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