1 /*
2 * Copyright (C) 2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 /*
18 * Verification-time map of data section items
19 */
20
21 #include "DexDataMap.h"
22 #include <safe_iop.h>
23 #include <stdlib.h>
24
25 /*
26 * Allocate and initialize a DexDataMap. Returns NULL on failure.
27 */
dexDataMapAlloc(u4 maxCount)28 DexDataMap* dexDataMapAlloc(u4 maxCount) {
29 /*
30 * Allocate a single chunk for the DexDataMap per se as well as the
31 * two arrays.
32 */
33 size_t size = 0;
34 DexDataMap* map = NULL;
35
36 /*
37 * Avoiding pulling in safe_iop for safe_iopf.
38 */
39 if (!safe_mul(&size, maxCount, sizeof(u4) + sizeof(u2)) ||
40 !safe_add(&size, size, sizeof(DexDataMap))) {
41 return NULL;
42 }
43
44 map = (DexDataMap*) malloc(size);
45
46 if (map == NULL) {
47 return NULL;
48 }
49
50 map->count = 0;
51 map->max = maxCount;
52 map->offsets = (u4*) (map + 1);
53 map->types = (u2*) (map->offsets + maxCount);
54
55 return map;
56 }
57
58 /*
59 * Free a DexDataMap.
60 */
dexDataMapFree(DexDataMap * map)61 void dexDataMapFree(DexDataMap* map) {
62 /*
63 * Since everything got allocated together, everything can be freed
64 * in one fell swoop. Also, free(NULL) is a nop (per spec), so we
65 * don't have to worry about an explicit test for that.
66 */
67 free(map);
68 }
69
70 /*
71 * Add a new element to the map. The offset must be greater than the
72 * all previously added offsets.
73 */
dexDataMapAdd(DexDataMap * map,u4 offset,u2 type)74 void dexDataMapAdd(DexDataMap* map, u4 offset, u2 type) {
75 assert(map != NULL);
76 assert(map->count < map->max);
77
78 if ((map->count != 0) &&
79 (map->offsets[map->count - 1] >= offset)) {
80 LOGE("Out-of-order data map offset: %#x then %#x",
81 map->offsets[map->count - 1], offset);
82 return;
83 }
84
85 map->offsets[map->count] = offset;
86 map->types[map->count] = type;
87 map->count++;
88 }
89
90 /*
91 * Get the type associated with the given offset. This returns -1 if
92 * there is no entry for the given offset.
93 */
dexDataMapGet(DexDataMap * map,u4 offset)94 int dexDataMapGet(DexDataMap* map, u4 offset) {
95 assert(map != NULL);
96
97 // Note: Signed type is important for max and min.
98 int min = 0;
99 int max = map->count - 1;
100 u4* offsets = map->offsets;
101
102 while (max >= min) {
103 int guessIdx = (min + max) >> 1;
104 u4 guess = offsets[guessIdx];
105
106 if (offset < guess) {
107 max = guessIdx - 1;
108 } else if (offset > guess) {
109 min = guessIdx + 1;
110 } else {
111 // We have a winner!
112 return map->types[guessIdx];
113 }
114 }
115
116 // No match.
117 return -1;
118 }
119
120 /*
121 * Verify that there is an entry in the map, mapping the given offset to
122 * the given type. This will return true if such an entry exists and
123 * return false as well as log an error if not.
124 */
dexDataMapVerify(DexDataMap * map,u4 offset,u2 type)125 bool dexDataMapVerify(DexDataMap* map, u4 offset, u2 type) {
126 int found = dexDataMapGet(map, offset);
127
128 if (found == type) {
129 return true;
130 }
131
132 if (found < 0) {
133 LOGE("No data map entry found @ %#x; expected %x",
134 offset, type);
135 } else {
136 LOGE("Unexpected data map entry @ %#x: expected %x, found %x",
137 offset, type, found);
138 }
139
140 return false;
141 }
142