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