runtime/maptable.mm

   1 /*
   2  * Copyright (c) 1999-2003, 2005-2007 Apple Inc.  All Rights Reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23 /*      maptable.m
  24         Copyright 1990-1996 NeXT Software, Inc.
  25         Created by Bertrand Serlet, August 1990
  26  */
  27
  28
  29 #include <string.h>
  30 #include <stdlib.h>
  31 #include <stdio.h>
  32
  33 #include "objc-private.h"
  34 #include "maptable.h"
  35 #include "hashtable2.h"
  36
  37
  38 /******         Macros and utilities    ****************************/
  39
  40 #if defined(DEBUG)
  41     #define INLINE
  42 #else
  43     #define INLINE inline
  44 #endif
  45
  46 typedef struct _MapPair {
  47     const void  *key;
  48     const void  *value;
  49 } MapPair;
  50
  51 static INLINE unsigned xorHash(unsigned hash) {
  52     unsigned xored = (hash & 0xffff) ^ (hash >> 16);
  53     return ((xored * 65521) + hash);
  54 }
  55
  56 static INLINE unsigned bucketOf(NXMapTable *table, const void *key) {
  57     unsigned    hash = (table->prototype->hash)(table, key);
  58     return hash & table->nbBucketsMinusOne;
  59 }
  60
  61 static INLINE int isEqual(NXMapTable *table, const void *key1, const void *key2) {
  62     return (key1 == key2) ? 1 : (table->prototype->isEqual)(table, key1, key2);
  63 }
  64
  65 static INLINE unsigned nextIndex(NXMapTable *table, unsigned index) {
  66     return (index + 1) & table->nbBucketsMinusOne;
  67 }
  68
  69 static INLINE void *allocBuckets(void *z, unsigned nb) {
  70     MapPair     *pairs = 1+(MapPair *)malloc_zone_malloc((malloc_zone_t *)z, ((nb+1) * sizeof(MapPair)));
  71     MapPair     *pair = pairs;
  72     while (nb--) { pair->key = NX_MAPNOTAKEY; pair->value = NULL; pair++; }
  73     return pairs;
  74 }
  75
  76 static INLINE void freeBuckets(void *p) {
  77     free(-1+(MapPair *)p);
  78 }
  79
  80 /*****          Global data and bootstrap       **********************/
  81
  82 static int isEqualPrototype (const void *info, const void *data1, const void *data2) {
  83     NXHashTablePrototype        *proto1 = (NXHashTablePrototype *) data1;
  84     NXHashTablePrototype        *proto2 = (NXHashTablePrototype *) data2;
  85
  86     return (proto1->hash == proto2->hash) && (proto1->isEqual == proto2->isEqual) && (proto1->free == proto2->free) && (proto1->style == proto2->style);
  87     };
  88
  89 static uintptr_t hashPrototype (const void *info, const void *data) {
  90     NXHashTablePrototype        *proto = (NXHashTablePrototype *) data;
  91
  92     return NXPtrHash(info, (void*)proto->hash) ^ NXPtrHash(info, (void*)proto->isEqual) ^ NXPtrHash(info, (void*)proto->free) ^ (uintptr_t) proto->style;
  93     };
  94
  95 static NXHashTablePrototype protoPrototype = {
  96     hashPrototype, isEqualPrototype, NXNoEffectFree, 0
  97 };
  98
  99 static NXHashTable *prototypes = NULL;
 100         /* table of all prototypes */
 101
 102 /****           Fundamentals Operations                 **************/
 103
 104 NXMapTable *NXCreateMapTableFromZone(NXMapTablePrototype prototype, unsigned capacity, void *z) {
 105     NXMapTable                  *table = (NXMapTable *)malloc_zone_malloc((malloc_zone_t *)z, sizeof(NXMapTable));
 106     NXMapTablePrototype         *proto;
 107     if (! prototypes) prototypes = NXCreateHashTable(protoPrototype, 0, NULL);
 108     if (! prototype.hash || ! prototype.isEqual || ! prototype.free || prototype.style) {
 109         _objc_inform("*** NXCreateMapTable: invalid creation parameters\n");
 110         return NULL;
 111     }
 112     proto = (NXMapTablePrototype *)NXHashGet(prototypes, &prototype);
 113     if (! proto) {
 114         proto = (NXMapTablePrototype *)malloc(sizeof(NXMapTablePrototype));
 115         *proto = prototype;
 116         (void)NXHashInsert(prototypes, proto);
 117     }
 118     table->prototype = proto; table->count = 0;
 119     table->nbBucketsMinusOne = exp2u(log2u(capacity)+1) - 1;
 120     table->buckets = allocBuckets(z, table->nbBucketsMinusOne + 1);
 121     return table;
 122 }
 123
 124 NXMapTable *NXCreateMapTable(NXMapTablePrototype prototype, unsigned capacity) {
 125     return NXCreateMapTableFromZone(prototype, capacity, malloc_default_zone());
 126 }
 127
 128 void NXFreeMapTable(NXMapTable *table) {
 129     NXResetMapTable(table);
 130     freeBuckets(table->buckets);
 131     free(table);
 132 }
 133
 134 void NXResetMapTable(NXMapTable *table) {
 135     MapPair     *pairs = (MapPair *)table->buckets;
 136     void        (*freeProc)(struct _NXMapTable *, void *, void *) = table->prototype->free;
 137     unsigned    index = table->nbBucketsMinusOne + 1;
 138     while (index--) {
 139         if (pairs->key != NX_MAPNOTAKEY) {
 140             freeProc(table, (void *)pairs->key, (void *)pairs->value);
 141             pairs->key = NX_MAPNOTAKEY; pairs->value = NULL;
 142         }
 143         pairs++;
 144     }
 145     table->count = 0;
 146 }
 147
 148 BOOL NXCompareMapTables(NXMapTable *table1, NXMapTable *table2) {
 149     if (table1 == table2) return YES;
 150     if (table1->count != table2->count) return NO;
 151     else {
 152         const void *key;
 153         const void *value;
 154         NXMapState      state = NXInitMapState(table1);
 155         while (NXNextMapState(table1, &state, &key, &value)) {
 156             if (NXMapMember(table2, key, (void**)&value) == NX_MAPNOTAKEY) return NO;
 157         }
 158         return YES;
 159     }
 160 }
 161
 162 unsigned NXCountMapTable(NXMapTable *table) { return table->count; }
 163
 164 #if __x86_64__
 165 extern "C" void __NXMAPTABLE_CORRUPTED__
 166 (const void *table, const void *buckets, uint64_t count,
 167  uint64_t nbBucketsMinusOne, uint64_t badkeys, uint64_t index,
 168  uint64_t index2, uint64_t pairIndexes, const void *key1,
 169  const void *value1, const void *key2, const void *value2,
 170  const void *key3, const void *value3);
 171
 172 static int _mapStrIsEqual(NXMapTable *table, const void *key1, const void *key2);
 173
 174 asm("\n .text"
 175     "\n .private_extern ___NXMAPTABLE_CORRUPTED__"
 176     "\n ___NXMAPTABLE_CORRUPTED__:"
 177     // push a frame for the unwinder to see
 178     "\n pushq %rbp"
 179     "\n mov %rsp, %rbp"
 180     // push register parameters to the stack in reverse order
 181     "\n pushq %r9"
 182     "\n pushq %r8"
 183     "\n pushq %rcx"
 184     "\n pushq %rdx"
 185     "\n pushq %rsi"
 186     "\n pushq %rdi"
 187     // pop the pushed register parameters into their destinations
 188     "\n popq %rax"  // table
 189     "\n popq %rbx"  // buckets
 190     "\n popq %rcx"  // count
 191     "\n popq %rdx"  // nbBucketsMinusOne
 192     "\n popq %rdi"  // badkeys
 193     "\n popq %rsi"  // index
 194     // read stack parameters into their destinations
 195     "\n mov 0*8+16(%rbp), %r8"   // index2
 196     "\n mov 1*8+16(%rbp), %r9"   // pairIndexes
 197     "\n mov 2*8+16(%rbp), %r10"  // key1
 198     "\n mov 3*8+16(%rbp), %r11"  // value1
 199     "\n mov 4*8+16(%rbp), %r12"  // key2
 200     "\n mov 5*8+16(%rbp), %r13"  // value2
 201     "\n mov 6*8+16(%rbp), %r14"  // key3
 202     "\n mov 7*8+16(%rbp), %r15"  // value3
 203     "\n ud2");
 204 #endif
 205
 206 // Look for a particular case of data corruption (rdar://36373000)
 207 // and investigate it further before crashing.
 208 static void validateKey(NXMapTable *table, MapPair *pair,
 209                         unsigned index, unsigned index2)
 210 {
 211 #if __x86_64__
 212 #   define BADKEY ((void * _Nonnull)(0xfffffffffffffffeULL))
 213     if (pair->key != BADKEY  ||
 214         table->prototype->isEqual != _mapStrIsEqual)
 215     {
 216         return;
 217     }
 218
 219     _objc_inform_now_and_on_crash
 220         ("NXMapTable %p (%p) has invalid key/value pair %p->%p (%p)",
 221          table, table->buckets, pair->key, pair->value, pair);
 222     _objc_inform_now_and_on_crash
 223         ("table %p, buckets %p, count %u, nbNucketsMinusOne %u, "
 224          "prototype %p (hash %p, isEqual %p, free %p)",
 225          table, table->buckets, table->count, table->nbBucketsMinusOne,
 226          table->prototype, table->prototype->hash, table->prototype->isEqual,
 227          table->prototype->free);
 228
 229     // Count the number of bad keys in the table.
 230     MapPair *pairs = (MapPair *)table->buckets;
 231     unsigned badKeys = 0;
 232     for (unsigned i = 0; i < table->nbBucketsMinusOne+1; i++) {
 233         if (pairs[i].key == BADKEY) badKeys++;
 234     }
 235
 236     _objc_inform_now_and_on_crash("%u invalid keys in table", badKeys);
 237
 238     // Record some additional key pairs for posterity.
 239     unsigned pair2Index = nextIndex(table, index);
 240     unsigned pair3Index = nextIndex(table, pair2Index);
 241     MapPair *pair2 = pairs + pair2Index;
 242     MapPair *pair3 = pairs + pair3Index;
 243     uint64_t pairIndexes = ((uint64_t)pair2Index << 32) | pair3Index;
 244
 245     // Save a bunch of values to registers so we can see them in the crash log.
 246     __NXMAPTABLE_CORRUPTED__
 247         (// rax, rbx, rcx, rdx
 248          table, table->buckets, table->count, table->nbBucketsMinusOne,
 249          // rdi, rsi, skip rbp, skip rsp
 250          badKeys, index,
 251          // r8, r9, r10, r11
 252          index2, pairIndexes, pair->key, pair->value,
 253          // r12, r13, r14, r15
 254          pair2->key, pair2->value, pair3->key, pair3->value);
 255 #endif
 256 }
 257
 258 static INLINE void *_NXMapMember(NXMapTable *table, const void *key, void **value) {
 259     MapPair     *pairs = (MapPair *)table->buckets;
 260     unsigned    index = bucketOf(table, key);
 261     MapPair     *pair = pairs + index;
 262     if (pair->key == NX_MAPNOTAKEY) return NX_MAPNOTAKEY;
 263     validateKey(table, pair, index, index);
 264
 265     if (isEqual(table, pair->key, key)) {
 266         *value = (void *)pair->value;
 267         return (void *)pair->key;
 268     } else {
 269         unsigned        index2 = index;
 270         while ((index2 = nextIndex(table, index2)) != index) {
 271             pair = pairs + index2;
 272             if (pair->key == NX_MAPNOTAKEY) return NX_MAPNOTAKEY;
 273             validateKey(table, pair, index, index2);
 274             if (isEqual(table, pair->key, key)) {
 275                 *value = (void *)pair->value;
 276                 return (void *)pair->key;
 277             }
 278         }
 279         return NX_MAPNOTAKEY;
 280     }
 281 }
 282
 283 void *NXMapMember(NXMapTable *table, const void *key, void **value) {
 284     return _NXMapMember(table, key, value);
 285 }
 286
 287 void *NXMapGet(NXMapTable *table, const void *key) {
 288     void        *value;
 289     return (_NXMapMember(table, key, &value) != NX_MAPNOTAKEY) ? value : NULL;
 290 }
 291
 292 static void _NXMapRehash(NXMapTable *table) {
 293     MapPair     *pairs = (MapPair *)table->buckets;
 294     MapPair     *pair = pairs;
 295     unsigned    numBuckets = table->nbBucketsMinusOne + 1;
 296     unsigned    index = numBuckets;
 297     unsigned    oldCount = table->count;
 298
 299     table->nbBucketsMinusOne = 2 * numBuckets - 1;
 300     table->count = 0;
 301     table->buckets = allocBuckets(malloc_zone_from_ptr(table), table->nbBucketsMinusOne + 1);
 302     while (index--) {
 303         if (pair->key != NX_MAPNOTAKEY) {
 304             (void)NXMapInsert(table, pair->key, pair->value);
 305         }
 306         pair++;
 307     }
 308     if (oldCount != table->count)
 309         _objc_inform("*** maptable: count differs after rehashing; probably indicates a broken invariant: there are x and y such as isEqual(x, y) is TRUE but hash(x) != hash (y)\n");
 310     freeBuckets(pairs);
 311 }
 312
 313 void *NXMapInsert(NXMapTable *table, const void *key, const void *value) {
 314     MapPair     *pairs = (MapPair *)table->buckets;
 315     unsigned    index = bucketOf(table, key);
 316     MapPair     *pair = pairs + index;
 317     if (key == NX_MAPNOTAKEY) {
 318         _objc_inform("*** NXMapInsert: invalid key: -1\n");
 319         return NULL;
 320     }
 321
 322     unsigned numBuckets = table->nbBucketsMinusOne + 1;
 323
 324     if (pair->key == NX_MAPNOTAKEY) {
 325         pair->key = key; pair->value = value;
 326         table->count++;
 327         if (table->count * 4 > numBuckets * 3) _NXMapRehash(table);
 328         return NULL;
 329     }
 330
 331     if (isEqual(table, pair->key, key)) {
 332         const void      *old = pair->value;
 333         if (old != value) pair->value = value;/* avoid writing unless needed! */
 334         return (void *)old;
 335     } else if (table->count == numBuckets) {
 336         /* no room: rehash and retry */
 337         _NXMapRehash(table);
 338         return NXMapInsert(table, key, value);
 339     } else {
 340         unsigned        index2 = index;
 341         while ((index2 = nextIndex(table, index2)) != index) {
 342             pair = pairs + index2;
 343             if (pair->key == NX_MAPNOTAKEY) {
 344                 pair->key = key; pair->value = value;
 345                 table->count++;
 346                 if (table->count * 4 > numBuckets * 3) _NXMapRehash(table);
 347                 return NULL;
 348             }
 349             if (isEqual(table, pair->key, key)) {
 350                 const void      *old = pair->value;
 351                 if (old != value) pair->value = value;/* avoid writing unless needed! */
 352                 return (void *)old;
 353             }
 354         }
 355         /* no room: can't happen! */
 356         _objc_inform("**** NXMapInsert: bug\n");
 357         return NULL;
 358     }
 359 }
 360
 361 static int mapRemove = 0;
 362
 363 void *NXMapRemove(NXMapTable *table, const void *key) {
 364     MapPair     *pairs = (MapPair *)table->buckets;
 365     unsigned    index = bucketOf(table, key);
 366     MapPair     *pair = pairs + index;
 367     unsigned    chain = 1; /* number of non-nil pairs in a row */
 368     int         found = 0;
 369     const void  *old = NULL;
 370     if (pair->key == NX_MAPNOTAKEY) return NULL;
 371     mapRemove ++;
 372     /* compute chain */
 373     {
 374         unsigned        index2 = index;
 375         if (isEqual(table, pair->key, key)) {found ++; old = pair->value; }
 376         while ((index2 = nextIndex(table, index2)) != index) {
 377             pair = pairs + index2;
 378             if (pair->key == NX_MAPNOTAKEY) break;
 379             if (isEqual(table, pair->key, key)) {found ++; old = pair->value; }
 380             chain++;
 381         }
 382     }
 383     if (! found) return NULL;
 384     if (found != 1) _objc_inform("**** NXMapRemove: incorrect table\n");
 385     /* remove then reinsert */
 386     {
 387         MapPair buffer[16];
 388         MapPair *aux = (chain > 16) ? (MapPair *)malloc(sizeof(MapPair)*(chain-1)) : buffer;
 389         unsigned        auxnb = 0;
 390         int     nb = chain;
 391         unsigned        index2 = index;
 392         while (nb--) {
 393             pair = pairs + index2;
 394             if (! isEqual(table, pair->key, key)) aux[auxnb++] = *pair;
 395             pair->key = NX_MAPNOTAKEY; pair->value = NULL;
 396             index2 = nextIndex(table, index2);
 397         }
 398         table->count -= chain;
 399         if (auxnb != chain-1) _objc_inform("**** NXMapRemove: bug\n");
 400         while (auxnb--) NXMapInsert(table, aux[auxnb].key, aux[auxnb].value);
 401         if (chain > 16) free(aux);
 402     }
 403     return (void *)old;
 404 }
 405
 406 NXMapState NXInitMapState(NXMapTable *table) {
 407     NXMapState  state;
 408     state.index = table->nbBucketsMinusOne + 1;
 409     return state;
 410 }
 411
 412 int NXNextMapState(NXMapTable *table, NXMapState *state, const void **key, const void **value) {
 413     MapPair     *pairs = (MapPair *)table->buckets;
 414     while (state->index--) {
 415         MapPair *pair = pairs + state->index;
 416         if (pair->key != NX_MAPNOTAKEY) {
 417             *key = pair->key; *value = pair->value;
 418             return YES;
 419         }
 420     }
 421     return NO;
 422 }
 423
 424
 425 /***********************************************************************
 426 * NXMapKeyCopyingInsert
 427 * Like NXMapInsert, but strdups the key if necessary.
 428 * Used to prevent stale pointers when bundles are unloaded.
 429 **********************************************************************/
 430 void *NXMapKeyCopyingInsert(NXMapTable *table, const void *key, const void *value)
 431 {
 432     void *realKey;
 433     void *realValue = NULL;
 434
 435     if ((realKey = NXMapMember(table, key, &realValue)) != NX_MAPNOTAKEY) {
 436         // key DOES exist in table - use table's key for insertion
 437     } else {
 438         // key DOES NOT exist in table - copy the new key before insertion
 439         realKey = (void *)strdupIfMutable((char *)key);
 440     }
 441     return NXMapInsert(table, realKey, value);
 442 }
 443
 444
 445 /***********************************************************************
 446 * NXMapKeyFreeingRemove
 447 * Like NXMapRemove, but frees the existing key if necessary.
 448 * Used to prevent stale pointers when bundles are unloaded.
 449 **********************************************************************/
 450 void *NXMapKeyFreeingRemove(NXMapTable *table, const void *key)
 451 {
 452     void *realKey;
 453     void *realValue = NULL;
 454
 455     if ((realKey = NXMapMember(table, key, &realValue)) != NX_MAPNOTAKEY) {
 456         // key DOES exist in table - remove pair and free key
 457         realValue = NXMapRemove(table, realKey);
 458         // free the key from the table, not necessarily the one given
 459         freeIfMutable((char *)realKey);
 460         return realValue;
 461     } else {
 462         // key DOES NOT exist in table - nothing to do
 463         return NULL;
 464     }
 465 }
 466
 467
 468 /****           Conveniences            *************************************/
 469
 470 static unsigned _mapPtrHash(NXMapTable *table, const void *key) {
 471 #ifdef __LP64__
 472     return (unsigned)(((uintptr_t)key) >> 3);
 473 #else
 474     return ((uintptr_t)key) >> 2;
 475 #endif
 476 }
 477
 478 static unsigned _mapStrHash(NXMapTable *table, const void *key) {
 479     unsigned            hash = 0;
 480     unsigned char       *s = (unsigned char *)key;
 481     /* unsigned to avoid a sign-extend */
 482     /* unroll the loop */
 483     if (s) for (; ; ) {
 484         if (*s == '\0') break;
 485         hash ^= *s++;
 486         if (*s == '\0') break;
 487         hash ^= *s++ << 8;
 488         if (*s == '\0') break;
 489         hash ^= *s++ << 16;
 490         if (*s == '\0') break;
 491         hash ^= *s++ << 24;
 492     }
 493     return xorHash(hash);
 494 }
 495
 496 static int _mapPtrIsEqual(NXMapTable *table, const void *key1, const void *key2) {
 497     return key1 == key2;
 498 }
 499
 500 static int _mapStrIsEqual(NXMapTable *table, const void *key1, const void *key2) {
 501     if (key1 == key2) return YES;
 502     if (! key1) return ! strlen ((char *) key2);
 503     if (! key2) return ! strlen ((char *) key1);
 504     if (((char *) key1)[0] != ((char *) key2)[0]) return NO;
 505     return (strcmp((char *) key1, (char *) key2)) ? NO : YES;
 506 }
 507
 508 static void _mapNoFree(NXMapTable *table, void *key, void *value) {}
 509
 510 const NXMapTablePrototype NXPtrValueMapPrototype = {
 511     _mapPtrHash, _mapPtrIsEqual, _mapNoFree, 0
 512 };
 513
 514 const NXMapTablePrototype NXStrValueMapPrototype = {
 515     _mapStrHash, _mapStrIsEqual, _mapNoFree, 0
 516 };
 517
 518
 519 #if !__OBJC2__  &&  !TARGET_OS_WIN32
 520
 521 /* This only works with class Object, which is unavailable. */
 522
 523 /* Method prototypes */
 524 @interface DoesNotExist
 525 + (id)class;
 526 + (id)initialize;
 527 - (id)description;
 528 - (const char *)UTF8String;
 529 - (unsigned long)hash;
 530 - (BOOL)isEqual:(id)object;
 531 - (void)free;
 532 @end
 533
 534 static unsigned _mapObjectHash(NXMapTable *table, const void *key) {
 535     return [(id)key hash];
 536 }
 537
 538 static int _mapObjectIsEqual(NXMapTable *table, const void *key1, const void *key2) {
 539     return [(id)key1 isEqual:(id)key2];
 540 }
 541
 542 static void _mapObjectFree(NXMapTable *table, void *key, void *value) {
 543     [(id)key free];
 544 }
 545
 546 const NXMapTablePrototype NXObjectMapPrototype = {
 547     _mapObjectHash, _mapObjectIsEqual, _mapObjectFree, 0
 548 };
 549
 550 #endif