1 /* 2 * Copyright (c) 2000 Apple Computer, Inc. All rights reserved. 3 * 4 * @APPLE_LICENSE_HEADER_START@ 5 * 6 * The contents of this file constitute Original Code as defined in and 7 * are subject to the Apple Public Source License Version 1.1 (the 8 * "License"). You may not use this file except in compliance with the 9 * License. Please obtain a copy of the License at 10 * http://www.apple.com/publicsource and read it before using this file. 11 * 12 * This Original Code and all software distributed under the License are 13 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER 14 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 15 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 16 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the 17 * License for the specific language governing rights and limitations 18 * under the License. 19 * 20 * @APPLE_LICENSE_HEADER_END@ 21 */ 22 /* IOSymbol.cpp created by gvdl on Fri 1998-11-17 */ 23 24 #include <sys/cdefs.h> 25 26 __BEGIN_DECLS 27 #include <kern/lock.h> 28 __END_DECLS 29 30 #include <libkern/c++/OSSymbol.h> 31 #include <libkern/c++/OSLib.h> 32 33 #define super OSString 34 35 typedef struct { int i, j; } OSSymbolPoolState; 36 37 #if OSALLOCDEBUG 38 extern "C" { 39 extern int debug_container_malloc_size; 40 }; 41 #define ACCUMSIZE(s) do { debug_container_malloc_size += (s); } while(0) 42 #else 43 #define ACCUMSIZE(s) 44 #endif 45 46 class OSSymbolPool 47 { 48 private: 49 static const unsigned int kInitBucketCount = 16; 50 51 typedef struct { unsigned int count; OSSymbol **symbolP; } Bucket; 52 53 Bucket *buckets; 54 unsigned int nBuckets; 55 unsigned int count; 56 mutex_t *poolGate; 57 58 static inline void hashSymbol(const char *s, 59 unsigned int *hashP, 60 unsigned int *lenP) 61 { 62 unsigned int hash = 0; 63 unsigned int len = 0; 64 65 /* Unroll the loop. */ 66 for (;;) { 67 if (!*s) break; len++; hash ^= *s++; 68 if (!*s) break; len++; hash ^= *s++ << 8; 69 if (!*s) break; len++; hash ^= *s++ << 16; 70 if (!*s) break; len++; hash ^= *s++ << 24; 71 } 72 *lenP = len; 73 *hashP = hash; 74 } 75 76 static unsigned long log2(unsigned int x); 77 static unsigned long exp2ml(unsigned int x); 78 79 void reconstructSymbols(); 80 81 public: 82 static void *operator new(size_t size); 83 static void operator delete(void *mem, size_t size); 84 85 OSSymbolPool() { }; 86 OSSymbolPool(const OSSymbolPool *old); 87 virtual ~OSSymbolPool(); 88 89 bool init(); 90 91 inline void closeGate() { mutex_lock(poolGate); }; 92 inline void openGate() { mutex_unlock(poolGate); }; 93 94 OSSymbol *findSymbol(const char *cString) const; 95 OSSymbol *insertSymbol(OSSymbol *sym); 96 void removeSymbol(const char *cString); 97 98 OSSymbolPoolState initHashState(); 99 OSSymbol *nextHashState(OSSymbolPoolState *stateP); 100 }; 101 102 void * OSSymbolPool::operator new(size_t size) 103 { 104 void *mem = (void *)kalloc(size); 105 ACCUMSIZE(size); 106 assert(mem); 107 bzero(mem, size); 108 109 return mem; 110 } 111 112 void OSSymbolPool::operator delete(void *mem, size_t size) 113 { 114 kfree((vm_offset_t)mem, size); 115 ACCUMSIZE(-size); 116 } 117 118 bool OSSymbolPool::init() 119 { 120 count = 0; 121 nBuckets = exp2ml(1 + log2(kInitBucketCount)); 122 buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket)); 123 ACCUMSIZE(nBuckets * sizeof(Bucket)); 124 if (!buckets) 125 return false; 126 127 bzero(buckets, nBuckets * sizeof(Bucket)); 128 129 poolGate = mutex_alloc(0); 130 131 return poolGate != 0; 132 } 133 134 OSSymbolPool::OSSymbolPool(const OSSymbolPool *old) 135 { 136 count = old->count; 137 nBuckets = old->nBuckets; 138 buckets = old->buckets; 139 140 poolGate = 0; // Do not duplicate the poolGate 141 } 142 143 OSSymbolPool::~OSSymbolPool() 144 { 145 if (buckets) { 146 kfree((vm_offset_t)buckets, nBuckets * sizeof(Bucket)); 147 ACCUMSIZE(-(nBuckets * sizeof(Bucket))); 148 } 149 150 if (poolGate) 151 kfree((vm_offset_t) poolGate, 36 * 4); 152 } 153 154 unsigned long OSSymbolPool::log2(unsigned int x) 155 { 156 unsigned long i; 157 158 for (i = 0; x > 1 ; i++) 159 x >>= 1; 160 return i; 161 } 162 163 unsigned long OSSymbolPool::exp2ml(unsigned int x) 164 { 165 return (1 << x) - 1; 166 } 167 168 OSSymbolPoolState OSSymbolPool::initHashState() 169 { 170 OSSymbolPoolState newState = { nBuckets, 0 }; 171 return newState; 172 } 173 174 OSSymbol *OSSymbolPool::nextHashState(OSSymbolPoolState *stateP) 175 { 176 Bucket *thisBucket = &buckets[stateP->i]; 177 178 while (!stateP->j) { 179 if (!stateP->i) 180 return 0; 181 stateP->i--; 182 thisBucket--; 183 stateP->j = thisBucket->count; 184 } 185 186 stateP->j--; 187 if (thisBucket->count == 1) 188 return (OSSymbol *) thisBucket->symbolP; 189 else 190 return thisBucket->symbolP[stateP->j]; 191 } 192 193 void OSSymbolPool::reconstructSymbols() 194 { 195 OSSymbolPool old(this); 196 OSSymbol *insert; 197 OSSymbolPoolState state; 198 199 nBuckets += nBuckets + 1; 200 count = 0; 201 buckets = (Bucket *) kalloc(nBuckets * sizeof(Bucket)); 202 ACCUMSIZE(nBuckets * sizeof(Bucket)); 203 /* @@@ gvdl: Zero test and panic if can't set up pool */ 204 bzero(buckets, nBuckets * sizeof(Bucket)); 205 206 state = old.initHashState(); 207 while ( (insert = old.nextHashState(&state)) ) 208 insertSymbol(insert); 209 } 210 211 OSSymbol *OSSymbolPool::findSymbol(const char *cString) const 212 { 213 Bucket *thisBucket; 214 unsigned int j, inLen, hash; 215 OSSymbol *probeSymbol, **list; 216 217 hashSymbol(cString, &hash, &inLen); inLen++; 218 thisBucket = &buckets[hash % nBuckets]; 219 j = thisBucket->count; 220 221 if (!j) 222 return 0; 223 224 if (j == 1) { 225 probeSymbol = (OSSymbol *) thisBucket->symbolP; 226 227 if (inLen == probeSymbol->length 228 && (strcmp(probeSymbol->string, cString) == 0) 229 && (probeSymbol->getRetainCount() >= 1)) // WRONG need when 230 return probeSymbol; 231 else 232 return 0; 233 } 234 235 for (list = thisBucket->symbolP; j--; list++) { 236 probeSymbol = *list; 237 if (inLen == probeSymbol->length 238 && (strcmp(probeSymbol->string, cString) == 0) 239 && (probeSymbol->getRetainCount() >= 1)) // WRONG need when 240 return probeSymbol; 241 } 242 243 return 0; 244 } 245 246 OSSymbol *OSSymbolPool::insertSymbol(OSSymbol *sym) 247 { 248 const char *cString = sym->string; 249 Bucket *thisBucket; 250 unsigned int j, inLen, hash; 251 OSSymbol *probeSymbol, **list; 252 253 hashSymbol(cString, &hash, &inLen); inLen++; 254 thisBucket = &buckets[hash % nBuckets]; 255 j = thisBucket->count; 256 257 if (!j) { 258 thisBucket->symbolP = (OSSymbol **) sym; 259 thisBucket->count++; 260 count++; 261 return 0; 262 } 263 264 if (j == 1) { 265 probeSymbol = (OSSymbol *) thisBucket->symbolP; 266 267 if (inLen == probeSymbol->length 268 && strcmp(probeSymbol->string, cString) == 0) 269 return probeSymbol; 270 271 list = (OSSymbol **) kalloc(2 * sizeof(OSSymbol *)); 272 ACCUMSIZE(2 * sizeof(OSSymbol *)); 273 /* @@@ gvdl: Zero test and panic if can't set up pool */ 274 list[0] = sym; 275 list[1] = probeSymbol; 276 thisBucket->symbolP = list; 277 thisBucket->count++; 278 count++; 279 if (count > nBuckets) 280 reconstructSymbols(); 281 282 return 0; 283 } 284 285 for (list = thisBucket->symbolP; j--; list++) { 286 probeSymbol = *list; 287 if (inLen == probeSymbol->length 288 && strcmp(probeSymbol->string, cString) == 0) 289 return probeSymbol; 290 } 291 292 j = thisBucket->count++; 293 count++; 294 list = (OSSymbol **) kalloc(thisBucket->count * sizeof(OSSymbol *)); 295 ACCUMSIZE(thisBucket->count * sizeof(OSSymbol *)); 296 /* @@@ gvdl: Zero test and panic if can't set up pool */ 297 list[0] = sym; 298 bcopy(thisBucket->symbolP, list + 1, j * sizeof(OSSymbol *)); 299 kfree((vm_offset_t)thisBucket->symbolP, j * sizeof(OSSymbol *)); 300 ACCUMSIZE(-(j * sizeof(OSSymbol *))); 301 thisBucket->symbolP = list; 302 if (count > nBuckets) 303 reconstructSymbols(); 304 305 return 0; 306 } 307 308 void OSSymbolPool::removeSymbol(const char *cString) 309 { 310 Bucket *thisBucket; 311 unsigned int j, inLen, hash; 312 OSSymbol *probeSymbol, **list; 313 314 hashSymbol(cString, &hash, &inLen); inLen++; 315 thisBucket = &buckets[hash % nBuckets]; 316 j = thisBucket->count; 317 list = thisBucket->symbolP; 318 319 if (!j) 320 return; 321 322 if (j == 1) { 323 probeSymbol = (OSSymbol *) list; 324 325 if (inLen == probeSymbol->length 326 && strcmp(probeSymbol->string, cString) == 0) { 327 thisBucket->symbolP = 0; 328 count--; 329 thisBucket->count--; 330 return; 331 } 332 return; 333 } 334 335 if (j == 2) { 336 probeSymbol = list[0]; 337 if (inLen == probeSymbol->length 338 && strcmp(probeSymbol->string, cString) == 0) { 339 thisBucket->symbolP = (OSSymbol **) list[1]; 340 kfree((vm_offset_t)list, 2 * sizeof(OSSymbol *)); 341 ACCUMSIZE(-(2 * sizeof(OSSymbol *))); 342 count--; 343 thisBucket->count--; 344 return; 345 } 346 347 probeSymbol = list[1]; 348 if (inLen == probeSymbol->length 349 && strcmp(probeSymbol->string, cString) == 0) { 350 thisBucket->symbolP = (OSSymbol **) list[0]; 351 kfree((vm_offset_t)list, 2 * sizeof(OSSymbol *)); 352 ACCUMSIZE(-(2 * sizeof(OSSymbol *))); 353 count--; 354 thisBucket->count--; 355 return; 356 } 357 return; 358 } 359 360 for (; j--; list++) { 361 probeSymbol = *list; 362 if (inLen == probeSymbol->length 363 && strcmp(probeSymbol->string, cString) == 0) { 364 365 list = (OSSymbol **) 366 kalloc((thisBucket->count-1) * sizeof(OSSymbol *)); 367 ACCUMSIZE((thisBucket->count-1) * sizeof(OSSymbol *)); 368 if (thisBucket->count-1 != j) 369 bcopy(thisBucket->symbolP, list, 370 (thisBucket->count-1-j) * sizeof(OSSymbol *)); 371 if (j) 372 bcopy(thisBucket->symbolP + thisBucket->count-j, 373 list + thisBucket->count-1-j, 374 j * sizeof(OSSymbol *)); 375 kfree((vm_offset_t)thisBucket->symbolP, thisBucket->count * sizeof(OSSymbol *)); 376 ACCUMSIZE(-(thisBucket->count * sizeof(OSSymbol *))); 377 thisBucket->symbolP = list; 378 count--; 379 thisBucket->count--; 380 return; 381 } 382 } 383 } 384 385 /* 386 ********************************************************************* 387 * From here on we are actually implementing the OSSymbol class 388 ********************************************************************* 389 */ 390 OSDefineMetaClassAndStructorsWithInit(OSSymbol, OSString, 391 OSSymbol::initialize()) 392 OSMetaClassDefineReservedUnused(OSSymbol, 0); 393 OSMetaClassDefineReservedUnused(OSSymbol, 1); 394 OSMetaClassDefineReservedUnused(OSSymbol, 2); 395 OSMetaClassDefineReservedUnused(OSSymbol, 3); 396 OSMetaClassDefineReservedUnused(OSSymbol, 4); 397 OSMetaClassDefineReservedUnused(OSSymbol, 5); 398 OSMetaClassDefineReservedUnused(OSSymbol, 6); 399 OSMetaClassDefineReservedUnused(OSSymbol, 7); 400 401 static OSSymbolPool *pool; 402 403 void OSSymbol::initialize() 404 { 405 pool = new OSSymbolPool; 406 assert(pool); 407 408 if (!pool->init()) { 409 delete pool; 410 assert(false); 411 }; 412 } 413 414 bool OSSymbol::initWithCStringNoCopy(const char *) { return false; } 415 bool OSSymbol::initWithCString(const char *) { return false; } 416 bool OSSymbol::initWithString(const OSString *) { return false; } 417 418 const OSSymbol *OSSymbol::withString(const OSString *aString) 419 { 420 // This string may be a OSSymbol already, cheap check. 421 if (OSDynamicCast(OSSymbol, aString)) { 422 aString->retain(); 423 return (const OSSymbol *) aString; 424 } 425 else if (((const OSSymbol *) aString)->flags & kOSStringNoCopy) 426 return OSSymbol::withCStringNoCopy(aString->getCStringNoCopy()); 427 else 428 return OSSymbol::withCString(aString->getCStringNoCopy()); 429 } 430 431 const OSSymbol *OSSymbol::withCString(const char *cString) 432 { 433 pool->closeGate(); 434 435 OSSymbol *newSymb = pool->findSymbol(cString); 436 if (newSymb) 437 newSymb->retain(); 438 else if ( (newSymb = new OSSymbol) ) { 439 if (newSymb->OSString::initWithCString(cString)) 440 pool->insertSymbol(newSymb); 441 else { 442 newSymb->free(); 443 newSymb = 0; 444 } 445 } 446 pool->openGate(); 447 448 return newSymb; 449 } 450 451 const OSSymbol *OSSymbol::withCStringNoCopy(const char *cString) 452 { 453 pool->closeGate(); 454 455 OSSymbol *newSymb = pool->findSymbol(cString); 456 if (newSymb) 457 newSymb->retain(); 458 else if ( (newSymb = new OSSymbol) ) { 459 if (newSymb->OSString::initWithCStringNoCopy(cString)) 460 pool->insertSymbol(newSymb); 461 else { 462 newSymb->free(); 463 newSymb = 0; 464 } 465 } 466 pool->openGate(); 467 468 return newSymb; 469 } 470 471 void OSSymbol::checkForPageUnload(void *startAddr, void *endAddr) 472 { 473 OSSymbol *probeSymbol; 474 OSSymbolPoolState state; 475 476 pool->closeGate(); 477 state = pool->initHashState(); 478 while ( (probeSymbol = pool->nextHashState(&state)) ) { 479 if (probeSymbol->string >= startAddr && probeSymbol->string < endAddr) { 480 const char *oldString = probeSymbol->string; 481 482 probeSymbol->string = (char *) kalloc(probeSymbol->length); 483 ACCUMSIZE(probeSymbol->length); 484 bcopy(oldString, probeSymbol->string, probeSymbol->length); 485 probeSymbol->flags &= ~kOSStringNoCopy; 486 } 487 } 488 pool->openGate(); 489 } 490 491 void OSSymbol::free() 492 { 493 pool->closeGate(); 494 pool->removeSymbol(string); 495 pool->openGate(); 496 497 super::free(); 498 } 499 500 bool OSSymbol::isEqualTo(const char *aCString) const 501 { 502 return super::isEqualTo(aCString); 503 } 504 505 bool OSSymbol::isEqualTo(const OSSymbol *aSymbol) const 506 { 507 return aSymbol == this; 508 } 509 510 bool OSSymbol::isEqualTo(const OSMetaClassBase *obj) const 511 { 512 OSSymbol * sym; 513 OSString * str; 514 515 if ((sym = OSDynamicCast(OSSymbol, obj))) 516 return isEqualTo(sym); 517 else if ((str = OSDynamicCast(OSString, obj))) 518 return super::isEqualTo(str); 519 else 520 return false; 521 } 522