libdex/DexDataMap.c

   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     if (!safe_mul(&size, maxCount, sizeof(u4) + sizeof(u2)) ||
  40         !safe_add(&size, size, sizeof(DexDataMap))) {
  41       return NULL;
  42     }
  43
  44     map = 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  */
  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  */
  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: 0x%x then 0x%x\n",
  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  */
  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  */
 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 @ 0x%x; expected %x\n",
 134                 offset, type);
 135     } else {
 136         LOGE("Unexpected data map entry @ 0x%x: expected %x, found %x\n",
 137                 offset, type, found);
 138     }
 139
 140     return false;
 141 }