fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * CDDL HEADER START
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * The contents of this file are subject to the terms of the
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * Common Development and Distribution License (the "License").
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * You may not use this file except in compliance with the License.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * See the License for the specific language governing permissions
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * and limitations under the License.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * When distributing Covered Code, include this CDDL HEADER in each
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * If applicable, add the following below this CDDL HEADER, with the
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * fields enclosed by brackets "[]" replaced with your own identifying
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * information: Portions Copyright [yyyy] [name of copyright owner]
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * CDDL HEADER END
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * Copyright 2008 Sun Microsystems, Inc. All rights reserved.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * Use is subject to license terms.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * _sdbc_hash_load - allocate all the locks for buckets.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte for (i = 0; i < _SD_HB_LOCKS; i++) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte mutex_init(&_sd_hb_locks[i], NULL, MUTEX_DRIVER, NULL);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * _sdbc_hash_unload - free all the locks for buckets.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte for (i = 0; i < _SD_HB_LOCKS; i++) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * _sdbc_hash_configure - create a hash table
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ARGUMENTS:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * num_ents - Number of entries (or hash buckets)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * htype - Type of memory to allocate.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * The address of the hash table just created
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * or zero in the event of failure.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * This routine rounds of the number of entries to the next higher
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * power of 2. Allocate the hash buckets and initializes the locks
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * and returns the hash table that is created.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * It is the caller's responsibility to save the hash_table and pass
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * it as a key for future accesses to the hash.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * It is also the caller's responsibility to destroy the hash table
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * when appropriate.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hash_table->ht_size = (1 << hash_table->ht_bits);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * this is where we compute the mask used in the hash function
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * the ht_nmask is basically an not of ht_mask used in hash
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hash_table->ht_nmask = (~0 & ~(hash_table->ht_mask));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if ((hash_table->ht_buckets = (_sd_hash_bucket_t *)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte bucket->hb_lock = &_sd_hb_locks[i % _SD_HB_LOCKS];
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * _sdbc_hash_deconfigure - deconfigure a hash table
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ARGUMENTS:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * hash_table - hash table that was created earlier on.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * this routine deallocates memory that was allocated during the
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * hash create.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte_sdbc_hash_deconfigure(_sd_hash_table_t *hash_table)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hash_table->ht_size * sizeof (_sd_hash_bucket_t));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte nsc_kmem_free(hash_table, sizeof (_sd_hash_table_t));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * _sd_hash_search - search the hash table for an entry
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ARGUMENTS:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * cd - device that we are interested in.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * block_num - block number we are interested in.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * hash_table - hash table to search in.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * returns a hash header if a match was found in the hash table
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * for the device & block_num.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * Else returns 0.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * This routine is called to check if a block already exists for
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * the device, block_num combination. If the block does not exist,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * then a new block needs to be allocated and inserted into the hash
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * table for future references.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte_sd_hash_search(int cd, nsc_off_t block_num, _sd_hash_table_t *table)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte for (hptr = bucket->hb_head; hptr; hptr = hnext) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * Save pointer for next before checking the seq counter.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * enforce ordering of load of hptr->hh_next
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * above and bucket->hb_seq below
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * To avoid looping forever, break out if a certain
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * limit is reached. Its okay to return miss
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * since the insert will do a proper search.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (++tries < MAX_HSEARCH_RETRIES) goto retry_search;
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if ((hptr->hh_cd == cd) && (hptr->hh_blk_num == block_num))
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte for (hptr = bucket->hb_head; hptr; hptr = hptr->hh_next) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if ((hptr->hh_cd == cd) && (hptr->hh_blk_num == block_num))
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * the list is ordered. If we go beyond our block, no
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * point searching
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * _sd_hash_insert - insert an entry into the hash table
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ARGUMENTS:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * cd - device that we are interested in.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * block_num - block number we are interested in.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * hptr - pointer to block that we are inserting.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * table - hash table to search in.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * Pointer to block that was passed in, except if the cd, block_num
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * already exists in the hash. Caller must check for return
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * not equal hptr.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * this routine inserts the hptr into the appropriate hash bucket and
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * sets the cd, block_num in the block for future references.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte cmn_err(CE_WARN, "_sd_err: hptr %p bucket %p already hashed",
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte for (p = bucket->hb_head; (p && (p->hh_blk_num <= block_num));
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if ((p->hh_cd == cd) && (p->hh_blk_num == block_num)) {
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * At this point, (p) points to the next higher block number or is
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * NULL. If it is NULL, we are queueing to the tail of list.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * Else, insert just before p
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if (_sd_hash_max_inlist < (int)++(bucket->hb_inlist))
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * _sd_hash_delete - delete an entry from the hash table
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ARGUMENTS:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * hptr - pointer to delete from hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * hash_table - hash table that was created earlier on.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * 0 on success. -1 on errors.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * this routine deletes a hash entry from the hash table.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte_sd_hash_delete(_sd_hash_hd_t *hptr, _sd_hash_table_t *table)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (-1);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* was FAST */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* was FAST */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte return (-1);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * Increment sequence counter on bucket. This will signal a lookup
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * to redo the lookup since we might have broken the link used
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * during the lookup.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* was FAST */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * _sd_hash_replace - replace 'old' with 'new' entry.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * ARGUMENTS:
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * old - pointer to block being deleted (to be anonymous)
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * new - pointer to block inserting in place.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * table - hash table to search in.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * pointer to inserted block.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * expects old & new to refer to same block.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte * new must not be already hashed.
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte_sd_hash_replace(_sd_hash_hd_t *old, _sd_hash_hd_t *new,
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte if ((old->hh_cd != new->hh_cd) || (old->hh_blk_num != new->hh_blk_num))
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte cmn_err(CE_PANIC, "_sd_hash_replace: mismatch %p %p",
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte cmn_err(CE_PANIC, "_sd_hash_replace: new %p already hashed",
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hptr = _sd_hash_insert(new->hh_cd, new->hh_blk_num, new, table);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* was FAST */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* was FAST */
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte hptr = _sd_hash_insert(new->hh_cd, new->hh_blk_num, new, table);
fcf3ce441efd61da9bb2884968af01cb7c1452ccJohn Forte /* was FAST */