OpenSolaris_b135/cmd/nscd/nscd_dbimpl.c
/*
* CDDL HEADER START
*
* The contents of this file are subject to the terms of the
* Common Development and Distribution License (the "License").
* You may not use this file except in compliance with the License.
*
* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
* or http://www.opensolaris.org/os/licensing.
* See the License for the specific language governing permissions
* and limitations under the License.
*
* When distributing Covered Code, include this CDDL HEADER in each
* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
* If applicable, add the following below this CDDL HEADER, with the
* fields enclosed by brackets "[]" replaced with your own identifying
* information: Portions Copyright [yyyy] [name of copyright owner]
*
* CDDL HEADER END
*/
/*
* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include "nscd_db.h"
/*
* This file implements the database functionality used by the
* switch and configuration components. The implementation is
* based on hash and has table. If the need arises in the future,
* the code in this file can be changed to use other algorithms.
* The following lists the functions implemented:
*
* _nscd_add_db_entry
* _nscd_delete_db_entry
* _nscd_get_db_entry
* _nscd_alloc_db
* _nscd_free_db
* _nscd_walk_db
* _nscd_delete_db_entry_cookie
*/
/*
* This structure defines an instance of the hash entry
* which implements the nscd database entry. The
* db_entry field should always be the first one in
* the structure.
*/
typedef struct nscd_hash {
nscd_db_entry_t db_entry;
struct nscd_hash *next_p;
struct nscd_hash *prev_p;
} nscd_hash_t;
/*
* This structure defines a nscd database which
* is implemented as an array of nscd_hash_t.
*/
struct nscd_db_s {
int array_size; /* number of elements in hash_tbl_p */
nscd_hash_t **hash_tbl_p;
};
/*
* This cookie structure is used to iterate through the
* database entries contained in a nscd database.
*/
struct cookie {
int idx; /* the current bucket */
nscd_hash_t *hash; /* the current hash entry */
nscd_db_t *db; /* the database */
};
/*
* FUNCTION: calc_hash
*
* Calculate a hash for a string based on the elf_hash
* algorithm, hash is case insensitive. Uses tolower
* instead of _tolower because of I18N.
*/
static unsigned long
calc_hash(
const char *str)
{
unsigned int hval = 0;
char ch;
while (*str != NULL) {
unsigned int g;
ch = (char)*str++;
if (isupper(ch))
ch = _tolower(ch);
hval = (hval << 4) + ch;
if ((g = (hval & 0xf0000000)) != 0)
hval ^= g >> 24;
hval &= ~g;
}
return ((unsigned long)hval);
}
/*
* FUNCTION: scan_hash
*
* Scan a hash table for a matching hash entry. Assume 'str' is
* not NULL. If option is NSCD_GET_NEXT_DB_ENTRY and id_num
* is less than zero, then treats the option as NSCD_GET_FIRST_DB_ENTRY.
*/
static const nscd_hash_t *
scan_hash(
int type,
const char *str,
const nscd_hash_t *idx_p,
nscd_db_option_t option,
int id_num)
{
int id_matched = 0;
nscd_db_entry_t *db_entry;
while (idx_p != NULL) {
db_entry = &((nscd_hash_t *)idx_p)->db_entry;
if (db_entry->type == type) {
if (strcasecmp(str, db_entry->name) == 0) {
switch (option) {
case NSCD_GET_FIRST_DB_ENTRY:
return (idx_p);
case NSCD_GET_EXACT_DB_ENTRY:
if (id_num == db_entry->id_num)
return (idx_p);
break;
case NSCD_GET_NEXT_DB_ENTRY:
if (id_num < 0)
return (idx_p);
if (id_matched == 1)
return (idx_p);
if (id_num == db_entry->id_num)
id_matched = 1;
break;
}
}
}
idx_p = idx_p->next_p;
}
return (NULL);
}
/*
* FUNCTION: _nscd_get_db_entry
*
* Find a nscd database entry from a nscd database.
*/
const nscd_db_entry_t *
_nscd_get_db_entry(
const nscd_db_t *db,
int type,
const char *str,
nscd_db_option_t option,
int id_num)
{
unsigned long hash;
const nscd_hash_t *idx_p, *hash_p;
if (db == NULL || str == NULL)
return (NULL);
hash = calc_hash(str);
idx_p = db->hash_tbl_p[hash % db->array_size];
hash_p = scan_hash(type, str, idx_p, option, id_num);
return (&hash_p->db_entry);
}
/*
* FUNCTION: _nscd_add_db_entry
*
* Add a nscd database entry to a nscd database. This function
* is not MT safe. The caller should lock the database to
* prevent concurrent updates done by other threads.
*/
nscd_rc_t
_nscd_add_db_entry(
nscd_db_t *db,
const char *str,
nscd_db_entry_t *entry,
nscd_db_option_t option)
{
int i;
unsigned long hash;
nscd_hash_t *next_p = NULL, *prev_p = NULL;
nscd_hash_t *idx_p, *hash_entry;
nscd_db_entry_t *db_entry;
/* find the bucket */
hash = calc_hash(str);
i = hash % db->array_size;
idx_p = db->hash_tbl_p[i];
/* can not replace nothing */
if (idx_p == NULL)
if (option == NSCD_ADD_DB_ENTRY_REPLACE)
return (NSCD_DB_ENTRY_NOT_FOUND);
while (idx_p != NULL) {
db_entry = &idx_p->db_entry;
switch (option) {
case NSCD_ADD_DB_ENTRY_FIRST:
next_p = idx_p;
goto add_entry;
case NSCD_ADD_DB_ENTRY_REPLACE:
if (db_entry->type != entry->type)
goto cont;
if (strcasecmp(db_entry->name, str) != 0)
goto cont;
if (db_entry->id_num == entry->id_num) {
prev_p = idx_p->prev_p;
next_p = idx_p->next_p;
free(idx_p);
goto add_entry;
}
goto cont;
case NSCD_ADD_DB_ENTRY_IF_NONE:
if (db_entry->type != entry->type)
break;
if (strcasecmp(db_entry->name, str) != 0)
break;
return (NSCD_DB_ENTRY_FOUND);
}
if (idx_p->next_p == NULL) {
if (option == NSCD_ADD_DB_ENTRY_LAST ||
option == NSCD_ADD_DB_ENTRY_IF_NONE) {
prev_p = idx_p;
goto add_entry;
}
}
cont:
idx_p = idx_p->next_p;
}
add_entry:
/*
* the nscd_entry_t field should be the first field
* in a nscd_hash_t
*/
hash_entry = (nscd_hash_t *)entry;
/* update the prev link list */
hash_entry->prev_p = prev_p;
if (prev_p == NULL)
db->hash_tbl_p[i] = hash_entry;
else
prev_p->next_p = hash_entry;
/* update the next link list */
hash_entry->next_p = next_p;
if (next_p != NULL)
next_p->prev_p = hash_entry;
return (NSCD_SUCCESS);
}
/*
* FUNCTION: _nscd_delete_db_entry
*
* Delete a nscd database entry from a nscd database. This
* function is not MT safe. The caller should lock the
* database to prevent concurrent updates done by other
* threads.
*/
nscd_rc_t
_nscd_delete_db_entry(
nscd_db_t *db,
int type,
const char *str,
nscd_db_option_t option,
int id_num)
{
int i;
int del_more = 0;
unsigned long hash;
nscd_hash_t *idx_p, *next_p = NULL, *prev_p = NULL;
nscd_db_entry_t *db_entry;
/* find the bucket */
hash = calc_hash(str);
i = hash % db->array_size;
idx_p = db->hash_tbl_p[i];
/* delete nothing always works */
if (idx_p == NULL)
return (NSCD_SUCCESS);
while (idx_p != NULL) {
db_entry = &idx_p->db_entry;
if (db_entry->type != type)
goto cont;
if (strcasecmp(db_entry->name, str) != 0)
goto cont;
switch (option) {
case NSCD_DEL_FIRST_DB_ENTRY:
prev_p = idx_p->prev_p;
next_p = idx_p->next_p;
del_more = 0;
break;
case NSCD_DEL_EXACT_DB_ENTRY:
if (db_entry->id_num == id_num) {
prev_p = idx_p->prev_p;
next_p = idx_p->next_p;
del_more = 0;
} else
goto cont;
break;
case NSCD_DEL_ALL_DB_ENTRY:
prev_p = idx_p->prev_p;
next_p = idx_p->next_p;
break;
}
if (prev_p == NULL)
db->hash_tbl_p[i] = next_p;
else
prev_p->next_p = next_p;
if (next_p != NULL)
next_p->prev_p = prev_p;
free(idx_p);
if (del_more == 0)
break;
/*
* only when option == NSCD_DEL_ALL_DB_ENTRY
* will we get here. next_p should be set to
* idx_p->next_p beforehand
*/
idx_p = next_p;
continue;
cont:
idx_p = idx_p->next_p;
}
return (NSCD_SUCCESS);
}
/*
* FUNCTION: _nscd_alloc_db_entry
*
* Allocate and return the memory for a database entry
* so the caller can insert data and then add it to the
* database.
*/
nscd_db_entry_t *
_nscd_alloc_db_entry(
int type,
const char *name,
int dataSize,
int num_data,
int num_array)
{
int size;
int array_o, data_o;
nscd_hash_t *hash;
void *p;
/* first part: hash data structure and name string */
size = sizeof (*hash) + strlen(name) + 1;
array_o = size = roundup(size);
/* second part: pointer array to data */
size += (num_data + num_array) * sizeof (void **);
size = roundup(size);
/* third part: actual data */
data_o = size;
size += dataSize;
/* allocate the memory */
hash = (nscd_hash_t *)calloc(1, size);
if (hash == NULL)
return (NULL);
/* init the entry based on caller's input */
hash->db_entry.num_data = num_data;
hash->db_entry.num_array = num_array;
hash->db_entry.type = type;
hash->db_entry.name = (char *)hash + sizeof (*hash);
p = (char *)hash + array_o;
hash->db_entry.data_array = (void **)p;
*(hash->db_entry.data_array) = (char *)hash + data_o;
(void) strcpy(hash->db_entry.name, name);
return (&hash->db_entry);
}
/*
* FUNCTION: _nscd_delete_db_entry_cookie
*
* Delete a database entry using the information from
* the input 'cookie'.
*/
void
_nscd_delete_db_entry_cookie(
nscd_db_t *db,
void **cookie)
{
nscd_hash_t *hp;
struct cookie *c;
/* snaity check */
if (cookie == NULL || *cookie == NULL || db == NULL)
return;
c = *cookie;
/* more snaity check */
if (db != c->db || c->hash == NULL ||
c->idx < 0 || c->idx >= db->array_size)
return;
/* retrieve the hash entry from the cookie */
hp = c->hash;
/*
* Update the next/previous link list.
* Need to update c->hash as well, in case
* the cookie is also used in a walk-db
* loop. This is to make sure that the
* next _nscd_walk_db() call will
* find the (updated) next hash entry in line.
*/
if (hp->prev_p == NULL) {
/*
* make sure the current bucket will be
* walked again if _nscd_walk_db is
* called next
*/
c->hash = NULL;
db->hash_tbl_p[c->idx] = hp->next_p;
c->idx--;
} else {
c->hash = hp->prev_p;
hp->prev_p->next_p = hp->next_p;
}
if (hp->next_p != NULL)
hp->next_p->prev_p = hp->prev_p;
/* delete the entry */
free(hp);
}
/*
* FUNCTION: _nscd_alloc_db
*
* Allocate the space for a nscd database.
*
* The input argument, size, indicates the size of the database.
* NSCD_DB_SIZE_LARGE specifies an bucket array of size 67,
* NSCD_DB_SIZE_MEDIUM specifies an bucket array of size 37,
* NSCD_DB_SIZE_SMALL specifies an bucket array of size 13,
* NSCD_DB_SIZE_TINY specifies an bucket array of size 3.
*/
nscd_db_t *
_nscd_alloc_db(
int size)
{
int sz;
nscd_db_t *db;
/* allocate the database */
db = (nscd_db_t *)calloc(1, sizeof (nscd_db_t));
if (db == NULL)
return (NULL);
/* allocate the bucket array */
if (size == NSCD_DB_SIZE_LARGE)
sz = 67;
else if (size == NSCD_DB_SIZE_MEDIUM)
sz = 37;
else if (size == NSCD_DB_SIZE_SMALL)
sz = 13;
else if (size == NSCD_DB_SIZE_TINY)
sz = 3;
db->hash_tbl_p = (nscd_hash_t **)calloc(sz + 1,
sizeof (nscd_hash_t *));
if (db->hash_tbl_p == NULL) {
free(db);
return (NULL);
}
db->array_size = sz;
return (db);
}
/*
* FUNCTION: _nscd_free_db
*
* Delete a nscd database.
*/
void
_nscd_free_db(
nscd_db_t *db)
{
int i;
nscd_hash_t *hp, *next_p;
/*
* find non-empty buckets and for each one of them,
* delete all the database entries in it's link list
*/
for (i = 0; i < db->array_size; i++) {
hp = db->hash_tbl_p[i];
while (hp != NULL) {
next_p = hp->next_p;
free(hp);
hp = next_p;
}
}
/* free the bucket array */
free(db->hash_tbl_p);
free(db);
}
/*
* FUNCTION: _nscd_walk_db
*
* Iterate through the database entries contained in
* a nscd database and return one entry at a time.
* The cookie structure is used to indicate the
* location of the returned entry for the next call
* to this function. For the very first call, *cookie
* should be set to NULL. For subsequent calls, the one
* returned by the previous call sould be used.
*/
nscd_db_entry_t *
_nscd_walk_db(
nscd_db_t *db,
void **cookie)
{
struct cookie *c;
/* sanity check */
if (cookie == NULL || db == NULL)
return (NULL);
if (*cookie != NULL) {
c = *cookie;
/*
* More sanity check. _nscd_delete_db_entry_cookie()
* could change c->idx to -1.
*/
if (db != c->db ||
c->idx < -1 || c->idx >= db->array_size)
return (NULL);
/* is there a next entry ? */
if (c->hash != NULL)
c->hash = c->hash->next_p;
/* yes, return it */
if (c->hash != NULL) {
return (&c->hash->db_entry);
}
} else {
c = (struct cookie *)calloc(1, sizeof (*c));
if (c == NULL)
return (NULL);
c->idx = -1;
c->hash = NULL;
c->db = db;
}
/* find the first non-empty bucket */
for (c->idx++; c->idx < db->array_size; c->idx++) {
c->hash = db->hash_tbl_p[c->idx];
if (c->hash != NULL)
break;
}
/* no (more) non-empty bucket, we are done */
if (c->hash == NULL) {
free(c);
*cookie = NULL;
return (NULL);
}
*cookie = c;
return (&c->hash->db_entry);
}