| OLD | NEW |
|---|
| (Empty) |
| 1 /* | |
| 2 * Copyright (c) 2011 The Native Client Authors. All rights reserved. | |
| 3 * Use of this source code is governed by a BSD-style license that can be | |
| 4 * found in the LICENSE file. | |
| 5 */ | |
| 6 | |
| 7 /* | |
| 8 * Compresses the tables for the table generator. | |
| 9 */ | |
| 10 | |
| 11 #ifndef NACL_TRUSTED_BUT_NOT_TCB | |
| 12 #error("This file is not meant for use in the TCB") | |
| 13 #endif | |
| 14 | |
| 15 #include <stdio.h> | |
| 16 #include <stdlib.h> | |
| 17 #include <assert.h> | |
| 18 #include <string.h> | |
| 19 | |
| 20 #include "native_client/src/trusted/validator/x86/decoder/generator/nc_compress.
h" | |
| 21 | |
| 22 #include "native_client/src/include/portability.h" | |
| 23 #include "native_client/src/include/portability_io.h" | |
| 24 #include "native_client/src/shared/utils/flags.h" | |
| 25 #include "native_client/src/shared/platform/nacl_log.h" | |
| 26 #include "native_client/src/trusted/validator/x86/x86_insts.h" | |
| 27 #include "native_client/src/trusted/validator/x86/decoder/generator/nacl_regsgen
.h" | |
| 28 #include "native_client/src/trusted/validator/x86/decoder/generator/ncdecode_for
ms.h" | |
| 29 #include "native_client/src/trusted/validator/x86/decoder/generator/ncdecode_st.
h" | |
| 30 | |
| 31 /* To turn on debugging of instruction decoding, change value of | |
| 32 * DEBUGGING to 1. | |
| 33 */ | |
| 34 #define DEBUGGING 0 | |
| 35 | |
| 36 #include "native_client/src/shared/utils/debugging.h" | |
| 37 | |
| 38 /* Returns true if the given instructions are (runtime) equal. */ | |
| 39 static Bool NaClInstSame(const NaClModeledInst* inst1, | |
| 40 const NaClModeledInst* inst2) { | |
| 41 if (inst1 == inst2) return TRUE; | |
| 42 if ((inst1 == NULL) || (inst2 == NULL)) return FALSE; | |
| 43 if (inst1->insttype != inst2->insttype) return FALSE; | |
| 44 if (inst1->flags != inst2->flags) return FALSE; | |
| 45 if (inst1->name != inst2->name) return FALSE; | |
| 46 if (inst1->opcode_ext != inst2->opcode_ext) return FALSE; | |
| 47 if (inst1->num_operands != inst2->num_operands) return FALSE; | |
| 48 if (inst1->operands != inst2->operands) return FALSE; | |
| 49 if (!NaClInstSame(inst1->next_rule, inst2->next_rule)) return FALSE; | |
| 50 return TRUE; | |
| 51 } | |
| 52 | |
| 53 /* Returns true if the given operands are equal. */ | |
| 54 static Bool NaClOpSame(const NaClOp* op1, const NaClOp* op2) { | |
| 55 if ((op1->kind == op2->kind) && (op1->flags == op2->flags)) { | |
| 56 if (NULL == op1->format_string) { | |
| 57 return NULL == op2->format_string; | |
| 58 } else if (NULL != op2->format_string) { | |
| 59 return 0 == strcmp(op1->format_string, op2->format_string); | |
| 60 } | |
| 61 } | |
| 62 return FALSE; | |
| 63 } | |
| 64 | |
| 65 /* Compress the operands in the given instruction. */ | |
| 66 static void NaClInstOpCompress(NaClInstTables* inst_tables, | |
| 67 NaClModeledInst* inst) { | |
| 68 size_t i; | |
| 69 Bool found = FALSE; /* until proven otherwise */ | |
| 70 if (NULL == inst) return; | |
| 71 if (inst->num_operands <= inst_tables->ops_compressed_size) { | |
| 72 /* Note: Be sure to not overflow compressed array by stopping when | |
| 73 * there is no more room for the operands of the given instruction. | |
| 74 */ | |
| 75 for (i = 0; | |
| 76 i <= inst_tables->ops_compressed_size - inst->num_operands; | |
| 77 ++i) { | |
| 78 size_t j; | |
| 79 Bool matches = TRUE; /* until proven otherwise */ | |
| 80 for (j = 0; j < inst->num_operands; ++j) { | |
| 81 if (!NaClOpSame(inst->operands + j, | |
| 82 inst_tables->ops_compressed + i + j)) { | |
| 83 matches = FALSE; | |
| 84 break; | |
| 85 } | |
| 86 } | |
| 87 if (matches) { | |
| 88 /* Operands already in compressed table, use copy. */ | |
| 89 inst->operands = inst_tables->ops_compressed + i; | |
| 90 found = TRUE; | |
| 91 break; | |
| 92 } | |
| 93 } | |
| 94 } | |
| 95 if (!found) { | |
| 96 /* If reached, not in compressed table. Add. */ | |
| 97 size_t new_size = | |
| 98 inst_tables->ops_compressed_size + inst->num_operands; | |
| 99 if (new_size > NACL_MAX_OPERANDS_TOTAL) { | |
| 100 NaClFatal("Not enough operand space to compress"); | |
| 101 } | |
| 102 for (i = 0; i < inst->num_operands; ++i) { | |
| 103 size_t index = inst_tables->ops_compressed_size + i; | |
| 104 inst_tables->ops_compressed[index].kind = inst->operands[i].kind; | |
| 105 inst_tables->ops_compressed[index].flags = inst->operands[i].flags; | |
| 106 inst_tables->ops_compressed[index].format_string = | |
| 107 inst->operands[i].format_string; | |
| 108 } | |
| 109 inst->operands = inst_tables->ops_compressed + | |
| 110 inst_tables->ops_compressed_size; | |
| 111 inst_tables->ops_compressed_size = new_size; | |
| 112 } | |
| 113 } | |
| 114 | |
| 115 /* Records the number of instructions that compression was attempted on. */ | |
| 116 static size_t num_uncompressed_instructions = 0; | |
| 117 | |
| 118 /* Compress the given instruction. */ | |
| 119 static NaClModeledInst* NaClInstCompress(NaClInstTables* inst_tables, | |
| 120 NaClModeledInst* inst) { | |
| 121 size_t i; | |
| 122 if (inst == NULL) return NULL; | |
| 123 ++num_uncompressed_instructions; | |
| 124 | |
| 125 /* First compress additional rules associated with the given | |
| 126 * instruction, so that when we compare this instruction, the | |
| 127 * compression of the additional rules will automatically be counted. | |
| 128 */ | |
| 129 inst->next_rule = NaClInstCompress(inst_tables, inst->next_rule); | |
| 130 | |
| 131 /* Compress the given instruction. */ | |
| 132 NaClInstOpCompress(inst_tables, inst); | |
| 133 | |
| 134 /* Now see if we already have such an instruction. If so, use it. */ | |
| 135 for (i = 0; i < inst_tables->inst_compressed_size; ++i) { | |
| 136 NaClModeledInst* comp_inst = inst_tables->inst_compressed[i]; | |
| 137 if (NaClInstSame(inst, comp_inst)) return comp_inst; | |
| 138 } | |
| 139 | |
| 140 /* If reached, no such instruction exists, put it into the table. */ | |
| 141 inst_tables->inst_compressed[i] = inst; | |
| 142 ++inst_tables->inst_compressed_size; | |
| 143 return inst; | |
| 144 } | |
| 145 | |
| 146 /* Compress operands of all instructions reachable from | |
| 147 * the given node. | |
| 148 */ | |
| 149 static void NaClOpNodeCompress(NaClInstTables* inst_tables, | |
| 150 NaClModeledInstNode* node) { | |
| 151 if (NULL == node) return; | |
| 152 node->matching_inst = NaClInstCompress(inst_tables, node->matching_inst); | |
| 153 NaClOpNodeCompress(inst_tables, node->success); | |
| 154 NaClOpNodeCompress(inst_tables, node->fail); | |
| 155 } | |
| 156 | |
| 157 /* Finds the index to use for the given instruction, assuming | |
| 158 * it is a compressed instruction. | |
| 159 */ | |
| 160 NaClOpcodeArrayOffset NaClFindInstIndex(NaClInstTables* inst_tables, | |
| 161 const NaClModeledInst* inst) { | |
| 162 size_t i; | |
| 163 if (NULL == inst) return NACL_OPCODE_NULL_OFFSET; | |
| 164 for (i = 0; i < inst_tables->inst_compressed_size; ++i) { | |
| 165 /* Fail if number of compressed instructions matches | |
| 166 * special NULL constant. | |
| 167 */ | |
| 168 if (i == NACL_OPCODE_NULL_OFFSET) { | |
| 169 continue; | |
| 170 } | |
| 171 if (inst == inst_tables->inst_compressed[i]) { | |
| 172 return (NaClOpcodeArrayOffset) i; | |
| 173 } | |
| 174 } | |
| 175 NaClFatal("Unable to find instruction index\n"); | |
| 176 /* NOT REACHED */ | |
| 177 return NACL_OPCODE_NULL_OFFSET; | |
| 178 } | |
| 179 | |
| 180 /* The type for an array of opcode instruction lookups, for a | |
| 181 * given prefix. | |
| 182 */ | |
| 183 typedef NaClOpcodeArrayOffset NaClInstOpcodeTable[NCDTABLESIZE]; | |
| 184 | |
| 185 /* Adds the given table into the array of prefix opcode entries. */ | |
| 186 static NaClPrefixOpcodeArrayOffset NaClOpcodeTableAdd( | |
| 187 NaClInstTables* inst_tables, | |
| 188 NaClInstOpcodeTable* table, | |
| 189 size_t table_size) { | |
| 190 size_t i; | |
| 191 size_t index; | |
| 192 | |
| 193 /* First see if we can overlay the table onto the existing | |
| 194 * lookup entries. | |
| 195 */ | |
| 196 if (table_size <= inst_tables->opcode_lookup_size) { | |
| 197 size_t cutoff = inst_tables->opcode_lookup_size - table_size; | |
| 198 for (i = 0; i <= cutoff; ++i) { | |
| 199 size_t j; | |
| 200 Bool found = TRUE; /* until proven otherwise. */ | |
| 201 for (j = 0; j < table_size; j++) { | |
| 202 if (inst_tables->opcode_lookup[i + j] != (*table)[j]) { | |
| 203 found = FALSE; | |
| 204 break; | |
| 205 } | |
| 206 } | |
| 207 if (found) { | |
| 208 return (NaClPrefixOpcodeArrayOffset) i; | |
| 209 } | |
| 210 } | |
| 211 } | |
| 212 | |
| 213 /* If reached, unable to overlay. Add to end of lookup entries. */ | |
| 214 if (inst_tables->opcode_lookup_size + table_size >= | |
| 215 NACL_MAX_PREFIX_OPCODE_ENTRIES) { | |
| 216 NaClFatal("prefix opcode lookup table overflow"); | |
| 217 } | |
| 218 index = inst_tables->opcode_lookup_size; | |
| 219 for (i = 0; i < table_size; ++i) { | |
| 220 inst_tables->opcode_lookup[index + i] = (*table)[i]; | |
| 221 } | |
| 222 inst_tables->opcode_lookup_size += table_size; | |
| 223 return (NaClOpcodeArrayOffset) index; | |
| 224 } | |
| 225 | |
| 226 /* Compress prefix opcode lookups for the given prefix. */ | |
| 227 static void NaClOpcodeTableCompressPrefix( | |
| 228 NaClInstTables* inst_tables, | |
| 229 NaClInstPrefix prefix) { | |
| 230 size_t i; | |
| 231 size_t table_size; | |
| 232 NaClInstOpcodeTable opcode_table; | |
| 233 uint8_t first_entry = 0; | |
| 234 uint8_t last_entry = NCDTABLESIZE - 1; | |
| 235 | |
| 236 /* Start by finding smallest region of opcodes for which | |
| 237 * the lookup values contain non-null entries. | |
| 238 */ | |
| 239 for (i = 0; i < NCDTABLESIZE; ++i) { | |
| 240 if (NULL == inst_tables->inst_table[i][prefix]) { | |
| 241 first_entry = (uint8_t) i; | |
| 242 } else { | |
| 243 break; | |
| 244 } | |
| 245 } | |
| 246 for (i = last_entry; ; --i) { | |
| 247 if (NULL == inst_tables->inst_table[i][prefix]) { | |
| 248 last_entry = (uint8_t) i; | |
| 249 if (i == first_entry) break; | |
| 250 } else { | |
| 251 break; | |
| 252 } | |
| 253 if (i == 0) break; /* Added to deal with underflow. */ | |
| 254 } | |
| 255 | |
| 256 /* Define only values for the region found. */ | |
| 257 table_size = (last_entry - first_entry) + 1; | |
| 258 | |
| 259 /* Fill in remaining values. */ | |
| 260 for (i = 0; i < table_size; ++i) { | |
| 261 opcode_table[i] = NaClFindInstIndex( | |
| 262 inst_tables, | |
| 263 inst_tables->inst_table[(int) first_entry + i][prefix]); | |
| 264 } | |
| 265 | |
| 266 /* Install the minimized table into the compressed data structures. */ | |
| 267 inst_tables->opcode_lookup_first[prefix] = first_entry; | |
| 268 inst_tables->opcode_lookup_last[prefix] = last_entry; | |
| 269 inst_tables->opcode_lookup_entry[prefix] = | |
| 270 NaClOpcodeTableAdd(inst_tables, &opcode_table, table_size); | |
| 271 } | |
| 272 | |
| 273 /* Compress the prefix/opcode tables. Generates a single array of entries, | |
| 274 * and triples defining what portion of that array corresponds to | |
| 275 * the lookup table for a given prefix. | |
| 276 */ | |
| 277 static void NaClOpcodeTableCompress(NaClInstTables* inst_tables) { | |
| 278 NaClInstPrefix prefix; | |
| 279 for (prefix = NoPrefix; prefix < NaClInstPrefixEnumSize; ++prefix) { | |
| 280 NaClOpcodeTableCompressPrefix(inst_tables, prefix); | |
| 281 } | |
| 282 } | |
| 283 | |
| 284 /* Walks over the modeled instructions and replaces duplicate | |
| 285 * operand entries. | |
| 286 */ | |
| 287 void NaClOpCompress(NaClInstTables* inst_tables) { | |
| 288 int i; | |
| 289 NaClInstPrefix prefix; | |
| 290 fprintf(stderr, "Note: %"NACL_PRIuS" operands before compression, ", | |
| 291 inst_tables->operands_size); | |
| 292 /* Compress the undefined instruction. Note: Must appear first, | |
| 293 * so that we know the location of undefined for static initialization | |
| 294 * in ncdis_decode_tables.c | |
| 295 */ | |
| 296 inst_tables->undefined_inst = | |
| 297 NaClInstCompress(inst_tables, inst_tables->undefined_inst); | |
| 298 | |
| 299 /* Compress all operands of instructions in the instruction opcode tables. */ | |
| 300 for (prefix = NoPrefix; prefix < NaClInstPrefixEnumSize; ++prefix) { | |
| 301 for (i = 0; i < NCDTABLESIZE; ++i) { | |
| 302 inst_tables->inst_table[i][prefix]= | |
| 303 NaClInstCompress(inst_tables, inst_tables->inst_table[i][prefix]); | |
| 304 } | |
| 305 } | |
| 306 | |
| 307 /* Compress all operands of instructions in the instruction trie. */ | |
| 308 NaClOpNodeCompress(inst_tables, inst_tables->inst_node_root); | |
| 309 fprintf(stderr, "%"NACL_PRIuS" after.\n", | |
| 310 inst_tables->ops_compressed_size); | |
| 311 fprintf(stderr, "Note: %"NACL_PRIuS" instruction before compression, " | |
| 312 "%"NACL_PRIuS" after.\n", | |
| 313 num_uncompressed_instructions, | |
| 314 inst_tables->inst_compressed_size); | |
| 315 | |
| 316 /* Compress the opcode table lookups. */ | |
| 317 NaClOpcodeTableCompress(inst_tables); | |
| 318 fprintf(stderr, "Note: %d opcode table entries before compression, " | |
| 319 "%"NACL_PRIuS" after.\n", | |
| 320 NCDTABLESIZE * NaClInstPrefixEnumSize, | |
| 321 inst_tables->opcode_lookup_size); | |
| 322 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 625923004:
Delete old x86 validator. (Closed)
Base URL: svn://svn.chromium.org/native_client/trunk/src/native_client