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 2008 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
24 */
25
26 #include <sys/types.h>
27 #include <sys/ksynch.h>
28 #include <sys/cmn_err.h>
29 #include <sys/kmem.h>
30 #include <sys/ddi.h>
31 #include <sys/nsc_thread.h>
32 #include <sys/nsctl/nsctl.h>
33
34 #include <sys/sdt.h> /* dtrace is S10 or later */
35
36 #include "sd_bcache.h"
37 #include "sd_hash.h"
38
39 #if defined(_SD_DEBUG)
40 int _sd_hash_max_inlist = 0;
41 #endif
42
43
44 #define _SD_HB_LOCKS 32
45 static kmutex_t _sd_hb_locks[_SD_HB_LOCKS];
46
47
48 /*
49 * _sdbc_hash_load - allocate all the locks for buckets.
50 *
51 *
52 */
53 int
_sdbc_hash_load(void)54 _sdbc_hash_load(void)
55 {
56 int i;
57 for (i = 0; i < _SD_HB_LOCKS; i++) {
58 mutex_init(&_sd_hb_locks[i], NULL, MUTEX_DRIVER, NULL);
59 }
60 return (0);
61 }
62
63 /*
64 * _sdbc_hash_unload - free all the locks for buckets.
65 *
66 *
67 */
68 void
_sdbc_hash_unload(void)69 _sdbc_hash_unload(void)
70 {
71 int i;
72 for (i = 0; i < _SD_HB_LOCKS; i++) {
73 mutex_destroy(&_sd_hb_locks[i]);
74 }
75 }
76
77
78 /*
79 * _sdbc_hash_configure - create a hash table
80 *
81 * ARGUMENTS:
82 * num_ents - Number of entries (or hash buckets)
83 * htype - Type of memory to allocate.
84 *
85 * RETURNS:
86 * The address of the hash table just created
87 * or zero in the event of failure.
88 *
89 * USAGE:
90 * This routine rounds of the number of entries to the next higher
91 * power of 2. Allocate the hash buckets and initializes the locks
92 * and returns the hash table that is created.
93 * It is the caller's responsibility to save the hash_table and pass
94 * it as a key for future accesses to the hash.
95 * It is also the caller's responsibility to destroy the hash table
96 * when appropriate.
97 */
98
99
100 _sd_hash_table_t *
_sdbc_hash_configure(int num_ents)101 _sdbc_hash_configure(int num_ents)
102 {
103 _sd_hash_table_t *hash_table;
104 _sd_hash_bucket_t *bucket;
105 int i;
106 int get_high_bit(int);
107
108 if ((hash_table = (_sd_hash_table_t *)
109 nsc_kmem_zalloc(sizeof (_sd_hash_table_t),
110 KM_SLEEP, sdbc_hash_mem)) == NULL)
111 return (NULL);
112
113 hash_table->ht_bits = get_high_bit(num_ents);
114 hash_table->ht_size = (1 << hash_table->ht_bits);
115
116 /*
117 * this is where we compute the mask used in the hash function
118 * the ht_nmask is basically an not of ht_mask used in hash
119 * function.
120 */
121 hash_table->ht_mask = (hash_table->ht_size - 1);
122 hash_table->ht_nmask = (~0 & ~(hash_table->ht_mask));
123
124 if ((hash_table->ht_buckets = (_sd_hash_bucket_t *)
125 nsc_kmem_zalloc(hash_table->ht_size *
126 sizeof (_sd_hash_bucket_t), KM_SLEEP,
127 sdbc_hash_mem)) == NULL)
128 return (NULL);
129
130 for (i = 0; i < (hash_table->ht_size); i++) {
131 bucket = (hash_table->ht_buckets + i);
132
133 bucket->hb_lock = &_sd_hb_locks[i % _SD_HB_LOCKS];
134 bucket->hb_head = bucket->hb_tail = NULL;
135 bucket->hb_inlist = 0;
136 }
137
138 return (hash_table);
139 }
140
141
142 /*
143 * _sdbc_hash_deconfigure - deconfigure a hash table
144 *
145 * ARGUMENTS:
146 * hash_table - hash table that was created earlier on.
147 *
148 * RETURNS:
149 * None.
150 *
151 * USAGE:
152 * this routine deallocates memory that was allocated during the
153 * hash create.
154 */
155
156 void
_sdbc_hash_deconfigure(_sd_hash_table_t * hash_table)157 _sdbc_hash_deconfigure(_sd_hash_table_t *hash_table)
158 {
159 if (!hash_table)
160 return;
161
162 nsc_kmem_free(hash_table->ht_buckets,
163 hash_table->ht_size * sizeof (_sd_hash_bucket_t));
164
165 nsc_kmem_free(hash_table, sizeof (_sd_hash_table_t));
166 }
167
168 static int _sd_forced_hash_miss;
169 static int _sd_hash_collision;
170
171
172 /*
173 * _sd_hash_search - search the hash table for an entry
174 *
175 * ARGUMENTS:
176 * cd - device that we are interested in.
177 * block_num - block number we are interested in.
178 * hash_table - hash table to search in.
179 *
180 * RETURNS:
181 * returns a hash header if a match was found in the hash table
182 * for the device & block_num.
183 * Else returns 0.
184 *
185 * USAGE:
186 * This routine is called to check if a block already exists for
187 * the device, block_num combination. If the block does not exist,
188 * then a new block needs to be allocated and inserted into the hash
189 * table for future references.
190 */
191
192 _sd_hash_hd_t *
_sd_hash_search(int cd,nsc_off_t block_num,_sd_hash_table_t * table)193 _sd_hash_search(int cd, nsc_off_t block_num, _sd_hash_table_t *table)
194 {
195 int i;
196 _sd_hash_bucket_t *bucket;
197 _sd_hash_hd_t *hptr;
198 #if defined(_SD_HASH_OPTIMIZE)
199 #define MAX_HSEARCH_RETRIES 30
200 int tries = 0;
201 _sd_hash_hd_t *hnext;
202 unsigned int seq;
203
204 i = HASH(cd, block_num, table);
205 bucket = (table->ht_buckets + i);
206 retry_search:
207 seq = bucket->hb_seq;
208 for (hptr = bucket->hb_head; hptr; hptr = hnext) {
209 /*
210 * Save pointer for next before checking the seq counter.
211 */
212 hnext = hptr->hh_next;
213 /*
214 * enforce ordering of load of hptr->hh_next
215 * above and bucket->hb_seq below
216 */
217 sd_serialize();
218 if (bucket->hb_seq != seq) {
219 /*
220 * To avoid looping forever, break out if a certain
221 * limit is reached. Its okay to return miss
222 * since the insert will do a proper search.
223 */
224 if (++tries < MAX_HSEARCH_RETRIES) goto retry_search;
225 else {
226 _sd_forced_hash_miss++;
227 DTRACE_PROBE1(_sd_hash_search_end,
228 int, _sd_forced_hash_miss);
229 return (NULL);
230 }
231 }
232 if ((hptr->hh_cd == cd) && (hptr->hh_blk_num == block_num))
233 break;
234 if (hptr->hh_blk_num > block_num) {
235 DTRACE_PROBE1(_sd_hash_search_end,
236 _sd_hash_hd_t *, hptr);
237 return (NULL);
238 }
239 }
240
241 DTRACE_PROBE1(_sd_hash_search_end,
242 _sd_hash_hd_t *, hptr);
243 return (hptr);
244 #else
245
246 i = HASH(cd, block_num, table);
247 bucket = (table->ht_buckets + i);
248
249 mutex_enter(bucket->hb_lock);
250
251 for (hptr = bucket->hb_head; hptr; hptr = hptr->hh_next) {
252 if ((hptr->hh_cd == cd) && (hptr->hh_blk_num == block_num))
253 break;
254 /*
255 * the list is ordered. If we go beyond our block, no
256 * point searching
257 */
258 if (hptr->hh_blk_num > block_num) {
259 hptr = NULL;
260 break;
261 }
262 }
263 mutex_exit(bucket->hb_lock);
264
265 return (hptr);
266 #endif
267 }
268
269
270 /*
271 * _sd_hash_insert - insert an entry into the hash table
272 *
273 * ARGUMENTS:
274 * cd - device that we are interested in.
275 * block_num - block number we are interested in.
276 * hptr - pointer to block that we are inserting.
277 * table - hash table to search in.
278 *
279 * RETURNS:
280 * Pointer to block that was passed in, except if the cd, block_num
281 * already exists in the hash. Caller must check for return
282 * not equal hptr.
283 *
284 * USAGE:
285 * this routine inserts the hptr into the appropriate hash bucket and
286 * sets the cd, block_num in the block for future references.
287 */
288
289 _sd_hash_hd_t *
_sd_hash_insert(int cd,nsc_off_t block_num,_sd_hash_hd_t * hptr,_sd_hash_table_t * table)290 _sd_hash_insert(int cd,
291 nsc_off_t block_num,
292 _sd_hash_hd_t *hptr,
293 _sd_hash_table_t *table)
294 {
295 int i;
296 _sd_hash_hd_t *p;
297 _sd_hash_bucket_t *bucket;
298
299 i = HASH(cd, block_num, table);
300 bucket = (table->ht_buckets + i);
301
302 #if defined(_SD_DEBUG)
303 if (hptr->hh_hashed) {
304 cmn_err(CE_WARN, "_sd_err: hptr %p bucket %p already hashed",
305 hptr, bucket);
306 }
307 #endif
308 hptr->hh_cd = (ushort_t)cd;
309 hptr->hh_blk_num = block_num;
310
311 mutex_enter(bucket->hb_lock);
312
313 for (p = bucket->hb_head; (p && (p->hh_blk_num <= block_num));
314 p = p->hh_next) {
315 if ((p->hh_cd == cd) && (p->hh_blk_num == block_num)) {
316 mutex_exit(bucket->hb_lock);
317 _sd_hash_collision++;
318 DTRACE_PROBE2(_sd_hash_insert_end,
319 _sd_hash_hd_t *, p,
320 int, _sd_hash_collision);
321
322 return (p);
323 }
324 }
325 hptr->hh_hashed = 1;
326 /*
327 * At this point, (p) points to the next higher block number or is
328 * NULL. If it is NULL, we are queueing to the tail of list.
329 * Else, insert just before p
330 */
331 if (p) {
332 hptr->hh_next = p;
333 if ((hptr->hh_prev = p->hh_prev) != NULL)
334 p->hh_prev->hh_next = hptr;
335 else
336 bucket->hb_head = hptr;
337 p->hh_prev = hptr;
338 } else {
339 hptr->hh_next = NULL;
340 hptr->hh_prev = bucket->hb_tail;
341 if (bucket->hb_head)
342 bucket->hb_tail->hh_next = hptr;
343 else
344 bucket->hb_head = hptr;
345 bucket->hb_tail = hptr;
346 }
347 #if defined(_SD_HASH_OPTIMIZE)
348 bucket->hb_seq++;
349 #endif
350 #if defined(_SD_DEBUG)
351 if (_sd_hash_max_inlist < (int)++(bucket->hb_inlist))
352 _sd_hash_max_inlist = bucket->hb_inlist;
353 #endif
354 mutex_exit(bucket->hb_lock);
355
356 return (hptr);
357 }
358
359
360
361 /*
362 * _sd_hash_delete - delete an entry from the hash table
363 *
364 * ARGUMENTS:
365 * hptr - pointer to delete from hash table.
366 * hash_table - hash table that was created earlier on.
367 *
368 * RETURNS:
369 * 0 on success. -1 on errors.
370 *
371 * USAGE:
372 * this routine deletes a hash entry from the hash table.
373 */
374
375 int
_sd_hash_delete(_sd_hash_hd_t * hptr,_sd_hash_table_t * table)376 _sd_hash_delete(_sd_hash_hd_t *hptr, _sd_hash_table_t *table)
377 {
378 int i;
379 _sd_hash_bucket_t *bucket;
380
381 if (hptr->hh_hashed == 0) {
382 DTRACE_PROBE(_sd_hash_delete_end1);
383 return (-1);
384 }
385
386 i = HASH(hptr->hh_cd, hptr->hh_blk_num, table);
387 bucket = (table->ht_buckets + i);
388
389 /* was FAST */
390 mutex_enter(bucket->hb_lock);
391 if (hptr->hh_hashed == 0) {
392 /* was FAST */
393 mutex_exit(bucket->hb_lock);
394 DTRACE_PROBE(_sd_hash_delete_end2);
395 return (-1);
396 }
397 hptr->hh_hashed = 0;
398 #if defined(_SD_HASH_OPTIMIZE)
399 /*
400 * Increment sequence counter on bucket. This will signal a lookup
401 * to redo the lookup since we might have broken the link used
402 * during the lookup.
403 */
404 bucket->hb_seq++;
405 #endif
406
407 if (hptr->hh_prev)
408 hptr->hh_prev->hh_next = hptr->hh_next;
409 else
410 bucket->hb_head = hptr->hh_next;
411 if (hptr->hh_next)
412 hptr->hh_next->hh_prev = hptr->hh_prev;
413 else
414 bucket->hb_tail = hptr->hh_prev;
415 #if defined(_SD_DEBUG)
416 bucket->hb_inlist--;
417 #endif
418 /* was FAST */
419 mutex_exit(bucket->hb_lock);
420
421 return (0);
422 }
423
424 /*
425 * _sd_hash_replace - replace 'old' with 'new' entry.
426 *
427 * ARGUMENTS:
428 * old - pointer to block being deleted (to be anonymous)
429 * new - pointer to block inserting in place.
430 * table - hash table to search in.
431 *
432 * RETURNS:
433 * pointer to inserted block.
434 *
435 * USAGE:
436 * expects old & new to refer to same block.
437 * new must not be already hashed.
438 */
439
440 _sd_hash_hd_t *
_sd_hash_replace(_sd_hash_hd_t * old,_sd_hash_hd_t * new,_sd_hash_table_t * table)441 _sd_hash_replace(_sd_hash_hd_t *old, _sd_hash_hd_t *new,
442 _sd_hash_table_t *table)
443 {
444 int i;
445 _sd_hash_bucket_t *bucket;
446
447 if ((old->hh_cd != new->hh_cd) || (old->hh_blk_num != new->hh_blk_num))
448 cmn_err(CE_PANIC, "_sd_hash_replace: mismatch %p %p",
449 (void *)old, (void *)new);
450 if (new->hh_hashed)
451 cmn_err(CE_PANIC, "_sd_hash_replace: new %p already hashed",
452 (void *)new);
453 if (old->hh_hashed == 0) {
454 _sd_hash_hd_t *hptr;
455 hptr = _sd_hash_insert(new->hh_cd, new->hh_blk_num, new, table);
456
457 DTRACE_PROBE1(_sd_hash_replace_end,
458 _sd_hash_hd_t *, hptr);
459
460 return (hptr);
461 }
462
463 i = HASH(old->hh_cd, old->hh_blk_num, table);
464 bucket = (table->ht_buckets + i);
465
466 /* was FAST */
467 mutex_enter(bucket->hb_lock);
468 if (old->hh_hashed == 0) {
469 _sd_hash_hd_t *hptr;
470 /* was FAST */
471 mutex_exit(bucket->hb_lock);
472
473 hptr = _sd_hash_insert(new->hh_cd, new->hh_blk_num, new, table);
474
475 DTRACE_PROBE1(_sd_hash_replace_end,
476 _sd_hash_hd_t *, hptr);
477 return (hptr);
478 }
479 old->hh_hashed = 0;
480 new->hh_hashed = 1;
481 new->hh_prev = old->hh_prev;
482 new->hh_next = old->hh_next;
483
484 if (new->hh_prev)
485 new->hh_prev->hh_next = new;
486 else
487 bucket->hb_head = new;
488 if (new->hh_next)
489 new->hh_next->hh_prev = new;
490 else
491 bucket->hb_tail = new;
492 #if defined(_SD_HASH_OPTIMIZE)
493 bucket->hb_seq++;
494 #endif
495 /* was FAST */
496 mutex_exit(bucket->hb_lock);
497
498 return (new);
499 }
500