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 const u4 sizeOfItems = (u4) (sizeof(u4) + sizeof(u2));
40 if (!safe_mul(&size, maxCount, sizeOfItems) ||
41 !safe_add(&size, size, sizeof(DexDataMap))) {
42 return NULL;
43 }
44
45 map = (DexDataMap*) malloc(size);
46
47 if (map == NULL) {
48 return NULL;
49 }
50
51 map->count = 0;
52 map->max = maxCount;
53 map->offsets = (u4*) (map + 1);
54 map->types = (u2*) (map->offsets + maxCount);
55
56 return map;
57 }
58
59 /*
60 * Free a DexDataMap.
61 */
dexDataMapFree(DexDataMap * map)62 void dexDataMapFree(DexDataMap* map) {
63 /*
64 * Since everything got allocated together, everything can be freed
65 * in one fell swoop. Also, free(NULL) is a nop (per spec), so we
66 * don't have to worry about an explicit test for that.
67 */
68 free(map);
69 }
70
71 /*
72 * Add a new element to the map. The offset must be greater than the
73 * all previously added offsets.
74 */
dexDataMapAdd(DexDataMap * map,u4 offset,u2 type)75 void dexDataMapAdd(DexDataMap* map, u4 offset, u2 type) {
76 assert(map != NULL);
77 assert(map->count < map->max);
78
79 if ((map->count != 0) &&
80 (map->offsets[map->count - 1] >= offset)) {
81 ALOGE("Out-of-order data map offset: %#x then %#x",
82 map->offsets[map->count - 1], offset);
83 return;
84 }
85
86 map->offsets[map->count] = offset;
87 map->types[map->count] = type;
88 map->count++;
89 }
90
91 /*
92 * Get the type associated with the given offset. This returns -1 if
93 * there is no entry for the given offset.
94 */
dexDataMapGet(DexDataMap * map,u4 offset)95 int dexDataMapGet(DexDataMap* map, u4 offset) {
96 assert(map != NULL);
97
98 // Note: Signed type is important for max and min.
99 int min = 0;
100 int max = map->count - 1;
101 u4* offsets = map->offsets;
102
103 while (max >= min) {
104 int guessIdx = (min + max) >> 1;
105 u4 guess = offsets[guessIdx];
106
107 if (offset < guess) {
108 max = guessIdx - 1;
109 } else if (offset > guess) {
110 min = guessIdx + 1;
111 } else {
112 // We have a winner!
113 return map->types[guessIdx];
114 }
115 }
116
117 // No match.
118 return -1;
119 }
120
121 /*
122 * Verify that there is an entry in the map, mapping the given offset to
123 * the given type. This will return true if such an entry exists and
124 * return false as well as log an error if not.
125 */
dexDataMapVerify(DexDataMap * map,u4 offset,u2 type)126 bool dexDataMapVerify(DexDataMap* map, u4 offset, u2 type) {
127 int found = dexDataMapGet(map, offset);
128
129 if (found == type) {
130 return true;
131 }
132
133 if (found < 0) {
134 ALOGE("No data map entry found @ %#x; expected %x",
135 offset, type);
136 } else {
137 ALOGE("Unexpected data map entry @ %#x: expected %x, found %x",
138 offset, type, found);
139 }
140
141 return false;
142 }
143