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