1/* Copyright (C) 2007-2010 The Android Open Source Project
2**
3** This software is licensed under the terms of the GNU General Public
4** License version 2, as published by the Free Software Foundation, and
5** may be copied, distributed, and modified under those terms.
6**
7** This program is distributed in the hope that it will be useful,
8** but WITHOUT ANY WARRANTY; without even the implied warranty of
9** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10** GNU General Public License for more details.
11*/
12
13/*
14 * Contains declarations of structures and routines that implement a red-black
15 * tree (a map) of memory blocks allocated by the guest system. The map is
16 * organized in such a way, that each entry in the map describes a virtual
17 * address range that belongs to a memory block allocated in the guest's space.
18 * The range includes block's suffix and prefix, as well as block returned to
19 * malloc's caller. Map considers two blocks to be equal if their address ranges
20 * intersect in any part. Allocation descriptor maps are instantiated one per
21 * each process running on the guest system.
22 */
23
24#ifndef QEMU_MEMCHECK_MEMCHECK_MALLOC_MAP_H
25#define QEMU_MEMCHECK_MEMCHECK_MALLOC_MAP_H
26
27#include "sys-tree.h"
28#include "memcheck_common.h"
29
30#ifdef __cplusplus
31extern "C" {
32#endif
33
34/* Allocation descriptors map. */
35typedef struct AllocMap {
36    /* Head of the map. */
37    struct AllocMapEntry*   rbh_root;
38} AllocMap;
39
40// =============================================================================
41// Map API
42// =============================================================================
43
44/* Initializes allocation descriptors map.
45 * Param:
46 *  map - Allocation descriptors map to initialize.
47 */
48void allocmap_init(AllocMap* map);
49
50/* Inserts new (or replaces existing) entry in the allocation descriptors map.
51 * Insertion, or replacement is controlled by the value, passed to this routine
52 * with 'replaced' parameter. If this parameter is NULL, insertion will fail if
53 * a matching entry already exists in the map. If 'replaced' parameter is not
54 * NULL, and a matching entry exists in the map, content of the existing entry
55 * will be copied to the descriptor, addressed by 'replace' parameter, existing
56 * entry will be removed from the map, and new entry will be inserted.
57 * Param:
58 *  map - Allocation descriptors map where to insert new, or replace existing
59 *      entry.
60 *  desc - Allocation descriptor to insert to the map.
61 *  replaced - If not NULL, upon return from this routine contains descriptor
62 *      that has been replaced in the map with the new entry. Note that if this
63 *      routine returns with value other than RBT_MAP_RESULT_ENTRY_REPLACED,
64 *      content of the 'replaced' buffer is not defined, as no replacement has
65 *      actually occurred.
66 * Return
67 *  See RBTMapResult for the return codes.
68 */
69RBTMapResult allocmap_insert(AllocMap* map,
70                             const MallocDescEx* desc,
71                             MallocDescEx* replaced);
72
73/* Finds an entry in the allocation descriptors map that matches the given
74 * address.
75 * Param:
76 *  map - Allocation descriptors map where to search for an entry.
77 *  address - Virtual address in the guest's user space to find matching
78 *      entry for. Entry matches the address, if address is contained within
79 *      allocated memory range (including guarding areas), as defined by the
80 *      memory allocation descriptor for that entry.
81 *  block_size - Size of the block, beginning with 'address'.
82 * Return:
83 *  Pointer to the allocation descriptor found in a map entry, or NULL if no
84 *  matching entry has been found in the map.
85 */
86MallocDescEx* allocmap_find(const AllocMap* map,
87                            target_ulong address,
88                            uint32_t block_size);
89
90/* Pulls (finds and removes) an entry from the allocation descriptors map that
91 * matches the given address.
92 * Param:
93 *  map - Allocation descriptors map where to search for an entry.
94 *  address - Virtual address in the guest's user space to find matching
95 *      entry for. Entry matches the address, if address is contained within
96 *      allocated memory range (including guarding areas), as defined by the
97 *      memory allocation descriptor for that entry.
98 *  pulled - Upon successful return contains allocation descriptor data pulled
99 *      from the map.
100 * Return:
101 *  Zero if an allocation descriptor that matches the given address has
102 *  been pulled, or 1 if no matching entry has been found in the map.
103 */
104int allocmap_pull(AllocMap* map, target_ulong address, MallocDescEx* pulled);
105
106/* Pulls (removes) an entry from the head of the allocation descriptors map.
107 * Param:
108 *  map - Allocation descriptors map where to pull an entry from.
109 *  pulled - Upon successful return contains allocation descriptor data pulled
110 *      from the head of the map.
111 * Return:
112 *  Zero if an allocation descriptor has been pulled from the head of the map,
113 *  or 1 if map is empty.
114 */
115int allocmap_pull_first(AllocMap* map, MallocDescEx* pulled);
116
117/* Copies content of one memory allocation descriptors map to another.
118 * Param:
119 *  to - Map where to copy entries to.
120 *  from - Map where to copy entries from.
121 *  set_flags - Flags that should be set in the copied entry's 'flags' field.
122 *  celar_flags - Flags that should be cleared in the copied entry's 'flags'
123 *  field.
124 * Return:
125 *  Zero on success, or -1 on error.
126 */
127int allocmap_copy(AllocMap* to,
128                  const AllocMap* from,
129                  uint32_t set_flags,
130                  uint32_t clear_flags);
131
132/* Empties the map.
133 * Param:
134 *  map - Map to empty.
135 * Return:
136 *  Number of entries removed from the map.
137 */
138int allocmap_empty(AllocMap* map);
139
140#ifdef __cplusplus
141};  /* end of extern "C" */
142#endif
143
144#endif  // QEMU_MEMCHECK_MEMCHECK_MALLOC_MAP_H
145