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 */ 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 */ 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 */ 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 */ 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 */ 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