1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License (the "License"). 6 * You may not use this file except in compliance with the License. 7 * 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 * or http://www.opensolaris.org/os/licensing. 10 * See the License for the specific language governing permissions 11 * and limitations under the License. 12 * 13 * When distributing Covered Code, include this CDDL HEADER in each 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 * If applicable, add the following below this CDDL HEADER, with the 16 * fields enclosed by brackets "[]" replaced with your own identifying 17 * information: Portions Copyright [yyyy] [name of copyright owner] 18 * 19 * CDDL HEADER END 20 */ 21 /* 22 * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 23 * Use is subject to license terms. 24 */ 25 26 #pragma ident "%Z%%M% %I% %E% SMI" 27 28 #include <stdio.h> 29 #include <stdlib.h> 30 #include <string.h> 31 #include <ctype.h> 32 #include "nscd_db.h" 33 34 /* 35 * This file implements the database functionality used by the 36 * switch and configuration components. The implementation is 37 * based on hash and has table. If the need arises in the future, 38 * the code in this file can be changed to use other algorithms. 39 * The following lists the functions implemented: 40 * 41 * _nscd_add_db_entry 42 * _nscd_delete_db_entry 43 * _nscd_get_db_entry 44 * _nscd_alloc_db 45 * _nscd_free_db 46 * _nscd_walk_db 47 * _nscd_delete_db_entry_cookie 48 */ 49 50 /* 51 * This structure defines an instance of the hash entry 52 * which implements the nscd database entry. The 53 * db_entry field should always be the first one in 54 * the structure. 55 */ 56 typedef struct nscd_hash { 57 nscd_db_entry_t db_entry; 58 struct nscd_hash *next_p; 59 struct nscd_hash *prev_p; 60 } nscd_hash_t; 61 62 /* 63 * This structure defines a nscd database which 64 * is implemented as an array of nscd_hash_t. 65 */ 66 struct nscd_db_s { 67 int array_size; /* number of elements in hash_tbl_p */ 68 nscd_hash_t **hash_tbl_p; 69 }; 70 71 /* 72 * This cookie structure is used to iterate through the 73 * database entries contained in a nscd database. 74 */ 75 struct cookie { 76 int idx; /* the current bucket */ 77 nscd_hash_t *hash; /* the current hash entry */ 78 nscd_db_t *db; /* the database */ 79 }; 80 81 /* 82 * FUNCTION: calc_hash 83 * 84 * Calculate a hash for a string based on the elf_hash 85 * algorithm, hash is case insensitive. Uses tolower 86 * instead of _tolower because of I18N. 87 */ 88 static unsigned long 89 calc_hash( 90 const char *str) 91 { 92 unsigned int hval = 0; 93 char ch; 94 95 while (*str != NULL) { 96 unsigned int g; 97 98 ch = (char)*str++; 99 if (isupper(ch)) 100 ch = _tolower(ch); 101 hval = (hval << 4) + ch; 102 if ((g = (hval & 0xf0000000)) != 0) 103 hval ^= g >> 24; 104 hval &= ~g; 105 } 106 return ((unsigned long)hval); 107 } 108 109 /* 110 * FUNCTION: scan_hash 111 * 112 * Scan a hash table for a matching hash entry. Assume 'str' is 113 * not NULL. If option is NSCD_GET_NEXT_DB_ENTRY and id_num 114 * is less than zero, then treats the option as NSCD_GET_FIRST_DB_ENTRY. 115 */ 116 117 static const nscd_hash_t * 118 scan_hash( 119 int type, 120 const char *str, 121 const nscd_hash_t *idx_p, 122 nscd_db_option_t option, 123 int id_num) 124 { 125 int id_matched = 0; 126 nscd_db_entry_t *db_entry; 127 128 while (idx_p != NULL) { 129 db_entry = &((nscd_hash_t *)idx_p)->db_entry; 130 if (db_entry->type == type) { 131 if (strcasecmp(str, db_entry->name) == 0) { 132 switch (option) { 133 case NSCD_GET_FIRST_DB_ENTRY: 134 return (idx_p); 135 case NSCD_GET_EXACT_DB_ENTRY: 136 if (id_num == db_entry->id_num) 137 return (idx_p); 138 break; 139 case NSCD_GET_NEXT_DB_ENTRY: 140 if (id_num < 0) 141 return (idx_p); 142 if (id_matched == 1) 143 return (idx_p); 144 if (id_num == db_entry->id_num) 145 id_matched = 1; 146 break; 147 } 148 } 149 } 150 idx_p = idx_p->next_p; 151 } 152 return (NULL); 153 } 154 155 /* 156 * FUNCTION: _nscd_get_db_entry 157 * 158 * Find a nscd database entry from a nscd database. 159 */ 160 const nscd_db_entry_t * 161 _nscd_get_db_entry( 162 const nscd_db_t *db, 163 int type, 164 const char *str, 165 nscd_db_option_t option, 166 int id_num) 167 { 168 unsigned long hash; 169 const nscd_hash_t *idx_p, *hash_p; 170 171 if (db == NULL || str == NULL) 172 return (NULL); 173 174 hash = calc_hash(str); 175 idx_p = db->hash_tbl_p[hash % db->array_size]; 176 177 hash_p = scan_hash(type, str, idx_p, option, id_num); 178 179 return (&hash_p->db_entry); 180 } 181 182 /* 183 * FUNCTION: _nscd_add_db_entry 184 * 185 * Add a nscd database entry to a nscd database. This function 186 * is not MT safe. The caller should lock the database to 187 * prevent concurrent updates done by other threads. 188 */ 189 nscd_rc_t 190 _nscd_add_db_entry( 191 nscd_db_t *db, 192 const char *str, 193 nscd_db_entry_t *entry, 194 nscd_db_option_t option) 195 { 196 int i; 197 unsigned long hash; 198 nscd_hash_t *next_p = NULL, *prev_p = NULL; 199 nscd_hash_t *idx_p, *hash_entry; 200 nscd_db_entry_t *db_entry; 201 202 /* find the bucket */ 203 hash = calc_hash(str); 204 i = hash % db->array_size; 205 idx_p = db->hash_tbl_p[i]; 206 207 /* can not replace nothing */ 208 if (idx_p == NULL) 209 if (option == NSCD_ADD_DB_ENTRY_REPLACE) 210 return (NSCD_DB_ENTRY_NOT_FOUND); 211 212 while (idx_p != NULL) { 213 db_entry = &idx_p->db_entry; 214 switch (option) { 215 216 case NSCD_ADD_DB_ENTRY_FIRST: 217 next_p = idx_p; 218 goto add_entry; 219 220 case NSCD_ADD_DB_ENTRY_REPLACE: 221 if (db_entry->type != entry->type) 222 goto cont; 223 if (strcasecmp(db_entry->name, str) != 0) 224 goto cont; 225 226 if (db_entry->id_num == entry->id_num) { 227 prev_p = idx_p->prev_p; 228 next_p = idx_p->next_p; 229 free(idx_p); 230 goto add_entry; 231 } 232 goto cont; 233 234 case NSCD_ADD_DB_ENTRY_IF_NONE: 235 if (db_entry->type != entry->type) 236 break; 237 if (strcasecmp(db_entry->name, str) != 0) 238 break; 239 return (NSCD_DB_ENTRY_FOUND); 240 } 241 242 if (idx_p->next_p == NULL) { 243 if (option == NSCD_ADD_DB_ENTRY_LAST || 244 option == NSCD_ADD_DB_ENTRY_IF_NONE) { 245 prev_p = idx_p; 246 goto add_entry; 247 } 248 } 249 250 cont: 251 idx_p = idx_p->next_p; 252 } 253 254 add_entry: 255 256 /* 257 * the nscd_entry_t field should be the first field 258 * in a nscd_hash_t 259 */ 260 hash_entry = (nscd_hash_t *)entry; 261 262 /* update the prev link list */ 263 hash_entry->prev_p = prev_p; 264 if (prev_p == NULL) 265 db->hash_tbl_p[i] = hash_entry; 266 else 267 prev_p->next_p = hash_entry; 268 269 /* update the next link list */ 270 hash_entry->next_p = next_p; 271 if (next_p != NULL) 272 next_p->prev_p = hash_entry; 273 274 return (NSCD_SUCCESS); 275 } 276 277 /* 278 * FUNCTION: _nscd_delete_db_entry 279 * 280 * Delete a nscd database entry from a nscd database. This 281 * function is not MT safe. The caller should lock the 282 * database to prevent concurrent updates done by other 283 * threads. 284 */ 285 nscd_rc_t 286 _nscd_delete_db_entry( 287 nscd_db_t *db, 288 int type, 289 const char *str, 290 nscd_db_option_t option, 291 int id_num) 292 { 293 int i; 294 int del_more = 0; 295 unsigned long hash; 296 nscd_hash_t *idx_p, *next_p = NULL, *prev_p = NULL; 297 nscd_db_entry_t *db_entry; 298 299 /* find the bucket */ 300 hash = calc_hash(str); 301 i = hash % db->array_size; 302 idx_p = db->hash_tbl_p[i]; 303 304 /* delete nothing always works */ 305 if (idx_p == NULL) 306 return (NSCD_SUCCESS); 307 308 while (idx_p != NULL) { 309 db_entry = &idx_p->db_entry; 310 if (db_entry->type != type) 311 goto cont; 312 if (strcasecmp(db_entry->name, str) != 0) 313 goto cont; 314 315 switch (option) { 316 317 case NSCD_DEL_FIRST_DB_ENTRY: 318 prev_p = idx_p->prev_p; 319 next_p = idx_p->next_p; 320 del_more = 0; 321 break; 322 323 case NSCD_DEL_EXACT_DB_ENTRY: 324 if (db_entry->id_num == id_num) { 325 prev_p = idx_p->prev_p; 326 next_p = idx_p->next_p; 327 del_more = 0; 328 } else 329 goto cont; 330 break; 331 332 case NSCD_DEL_ALL_DB_ENTRY: 333 prev_p = idx_p->prev_p; 334 next_p = idx_p->next_p; 335 break; 336 } 337 338 if (prev_p == NULL) 339 db->hash_tbl_p[i] = next_p; 340 else 341 prev_p->next_p = next_p; 342 343 if (next_p != NULL) 344 next_p->prev_p = prev_p; 345 346 free(idx_p); 347 348 if (del_more == 0) 349 break; 350 /* 351 * only when option == NSCD_DEL_ALL_DB_ENTRY 352 * will we get here. next_p should be set to 353 * idx_p->next_p beforehand 354 */ 355 idx_p = next_p; 356 continue; 357 358 cont: 359 360 idx_p = idx_p->next_p; 361 } 362 363 return (NSCD_SUCCESS); 364 } 365 366 /* 367 * FUNCTION: _nscd_alloc_db_entry 368 * 369 * Allocate and return the memory for a database entry 370 * so the caller can insert data and then add it to the 371 * database. 372 */ 373 nscd_db_entry_t * 374 _nscd_alloc_db_entry( 375 int type, 376 const char *name, 377 int dataSize, 378 int num_data, 379 int num_array) 380 { 381 int size; 382 int array_o, data_o; 383 nscd_hash_t *hash; 384 void *p; 385 386 /* first part: hash data structure and name string */ 387 size = sizeof (*hash) + strlen(name) + 1; 388 array_o = size = roundup(size); 389 390 /* second part: pointer array to data */ 391 size += (num_data + num_array) * sizeof (void **); 392 size = roundup(size); 393 394 /* third part: actual data */ 395 data_o = size; 396 size += dataSize; 397 398 /* allocate the memory */ 399 hash = (nscd_hash_t *)calloc(1, size); 400 401 if (hash == NULL) 402 return (NULL); 403 404 /* init the entry based on caller's input */ 405 hash->db_entry.num_data = num_data; 406 hash->db_entry.num_array = num_array; 407 hash->db_entry.type = type; 408 hash->db_entry.name = (char *)hash + sizeof (*hash); 409 p = (char *)hash + array_o; 410 hash->db_entry.data_array = (void **)p; 411 *(hash->db_entry.data_array) = (char *)hash + data_o; 412 (void) strcpy(hash->db_entry.name, name); 413 414 return (&hash->db_entry); 415 } 416 417 /* 418 * FUNCTION: _nscd_delete_db_entry_cookie 419 * 420 * Delete a database entry using the information from 421 * the input 'cookie'. 422 */ 423 void 424 _nscd_delete_db_entry_cookie( 425 nscd_db_t *db, 426 void **cookie) 427 { 428 nscd_hash_t *hp; 429 struct cookie *c; 430 431 /* snaity check */ 432 if (cookie == NULL || *cookie == NULL || db == NULL) 433 return; 434 c = *cookie; 435 436 /* more snaity check */ 437 if (db != c->db || c->hash == NULL || 438 c->idx < 0 || c->idx >= db->array_size) 439 return; 440 441 /* retrieve the hash entry from the cookie */ 442 hp = c->hash; 443 444 /* 445 * Update the next/previous link list. 446 * Need to update c->hash as well, in case 447 * the cookie is also used in a walk-db 448 * loop. This is to make sure that the 449 * next _nscd_walk_db() call will 450 * find the (updated) next hash entry in line. 451 */ 452 if (hp->prev_p == NULL) { 453 /* 454 * make sure the current bucket will be 455 * walked again if _nscd_walk_db is 456 * called next 457 */ 458 c->hash = NULL; 459 db->hash_tbl_p[c->idx] = hp->next_p; 460 c->idx--; 461 462 } else { 463 c->hash = hp->prev_p; 464 hp->prev_p->next_p = hp->next_p; 465 } 466 if (hp->next_p != NULL) 467 hp->next_p->prev_p = hp->prev_p; 468 469 /* delete the entry */ 470 free(hp); 471 } 472 473 /* 474 * FUNCTION: _nscd_alloc_db 475 * 476 * Allocate the space for a nscd database. 477 * 478 * The input argument, size, indicates the size of the database. 479 * NSCD_DB_SIZE_LARGE specifies an bucket array of size 67, 480 * NSCD_DB_SIZE_MEDIUM specifies an bucket array of size 37, 481 * NSCD_DB_SIZE_SMALL specifies an bucket array of size 13, 482 * NSCD_DB_SIZE_TINY specifies an bucket array of size 3. 483 */ 484 nscd_db_t * 485 _nscd_alloc_db( 486 int size) 487 { 488 int sz; 489 nscd_db_t *db; 490 491 /* allocate the database */ 492 db = (nscd_db_t *)calloc(1, sizeof (nscd_db_t)); 493 if (db == NULL) 494 return (NULL); 495 496 /* allocate the bucket array */ 497 if (size == NSCD_DB_SIZE_LARGE) 498 sz = 67; 499 else if (size == NSCD_DB_SIZE_MEDIUM) 500 sz = 37; 501 else if (size == NSCD_DB_SIZE_SMALL) 502 sz = 13; 503 else if (size == NSCD_DB_SIZE_TINY) 504 sz = 3; 505 db->hash_tbl_p = (nscd_hash_t **)calloc(sz + 1, 506 sizeof (nscd_hash_t *)); 507 if (db->hash_tbl_p == NULL) { 508 free(db); 509 return (NULL); 510 } 511 512 db->array_size = sz; 513 514 return (db); 515 } 516 517 /* 518 * FUNCTION: _nscd_free_db 519 * 520 * Delete a nscd database. 521 */ 522 void 523 _nscd_free_db( 524 nscd_db_t *db) 525 { 526 int i; 527 nscd_hash_t *hp, *next_p; 528 529 /* 530 * find non-empty buckets and for each one of them, 531 * delete all the database entries in it's link list 532 */ 533 for (i = 0; i < db->array_size; i++) { 534 535 hp = db->hash_tbl_p[i]; 536 537 while (hp != NULL) { 538 next_p = hp->next_p; 539 free(hp); 540 hp = next_p; 541 } 542 } 543 544 /* free the bucket array */ 545 free(db->hash_tbl_p); 546 547 free(db); 548 } 549 550 /* 551 * FUNCTION: _nscd_walk_db 552 * 553 * Iterate through the database entries contained in 554 * a nscd database and return one entry at a time. 555 * The cookie structure is used to indicate the 556 * location of the returned entry for the next call 557 * to this function. For the very first call, *cookie 558 * should be set to NULL. For subsequent calls, the one 559 * returned by the previous call sould be used. 560 */ 561 nscd_db_entry_t * 562 _nscd_walk_db( 563 nscd_db_t *db, 564 void **cookie) 565 { 566 struct cookie *c; 567 568 /* sanity check */ 569 if (cookie == NULL || db == NULL) 570 return (NULL); 571 572 if (*cookie != NULL) { 573 574 c = *cookie; 575 576 /* 577 * More sanity check. _nscd_delete_db_entry_cookie() 578 * could change c->idx to -1. 579 */ 580 if (db != c->db || 581 c->idx < -1 || c->idx >= db->array_size) 582 return (NULL); 583 584 /* is there a next entry ? */ 585 if (c->hash != NULL) 586 c->hash = c->hash->next_p; 587 588 /* yes, return it */ 589 if (c->hash != NULL) { 590 return (&c->hash->db_entry); 591 } 592 } else { 593 c = (struct cookie *)calloc(1, sizeof (*c)); 594 if (c == NULL) 595 return (NULL); 596 c->idx = -1; 597 c->hash = NULL; 598 c->db = db; 599 } 600 601 /* find the first non-empty bucket */ 602 for (c->idx++; c->idx < db->array_size; c->idx++) { 603 c->hash = db->hash_tbl_p[c->idx]; 604 if (c->hash != NULL) 605 break; 606 } 607 608 /* no (more) non-empty bucket, we are done */ 609 if (c->hash == NULL) { 610 free(c); 611 *cookie = NULL; 612 return (NULL); 613 } 614 615 *cookie = c; 616 return (&c->hash->db_entry); 617 } 618