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 */
28DexDataMap* 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 */
61void 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 */
74void 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        ALOGE("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 */
94int 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 */
125bool 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        ALOGE("No data map entry found @ %#x; expected %x",
134                offset, type);
135    } else {
136        ALOGE("Unexpected data map entry @ %#x: expected %x, found %x",
137                offset, type, found);
138    }
139
140    return false;
141}
142