xref: /illumos-gate/usr/src/cmd/ndmpd/tlm/tlm_bitmap.c (revision d21cedec)
1 /*
2  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
3  * Use is subject to license terms.
4  */
5 
6 /*
7  * BSD 3 Clause License
8  *
9  * Copyright (c) 2007, The Storage Networking Industry Association.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  * 	- Redistributions of source code must retain the above copyright
15  *	  notice, this list of conditions and the following disclaimer.
16  *
17  * 	- Redistributions in binary form must reproduce the above copyright
18  *	  notice, this list of conditions and the following disclaimer in
19  *	  the documentation and/or other materials provided with the
20  *	  distribution.
21  *
22  *	- Neither the name of The Storage Networking Industry Association (SNIA)
23  *	  nor the names of its contributors may be used to endorse or promote
24  *	  products derived from this software without specific prior written
25  *	  permission.
26  *
27  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
28  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
31  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
32  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
33  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
34  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
35  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
36  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
37  * POSSIBILITY OF SUCH DAMAGE.
38  */
39 #include <sys/types.h>
40 #include <sys/queue.h>
41 #include <bitmap.h>
42 #include <fcntl.h>
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <string.h>
46 #include <time.h>
47 #include <unistd.h>
48 #include <tlm.h>
49 
50 
51 /*
52  * Hash table size.
53  */
54 #define	BMAP_HASH_SIZE		64
55 
56 
57 /*
58  * Maximum number of chunk that can be cached.
59  */
60 #define	BMAP_CHUNK_MAX		128
61 
62 
63 /*
64  * Size of bitmap table.
65  */
66 #define	BMAP_MAX	256
67 
68 
69 /*
70  * Bit_MAP Word SIZE.  This should be equal to 'sizeof (int)'.
71  */
72 #define	BMAP_WSIZE	(sizeof (int))
73 
74 
75 /*
76  * Bit_MAP Bit Per Word.
77  */
78 #define	BMAP_BPW	(BMAP_WSIZE * 8)
79 #define	BMAP_BPW_SHIFT	5
80 #define	BMAP_BPW_MASK	(~(~0ULL << BMAP_BPW_SHIFT))
81 
82 
83 /*
84  * Chunk of bit map in each node.
85  */
86 #define	BMAP_CHUNK_WORDS	1024
87 #define	BMAP_CHUNK_BYTES	(BMAP_CHUNK_WORDS * BMAP_WSIZE)
88 #define	BMAP_CHUNK_BITS		(BMAP_CHUNK_WORDS * BMAP_BPW)
89 #define	BMAP_CHUNK_NO(p)	((p) / BMAP_CHUNK_BITS)
90 #define	BMAP_CHUNK_OFF(p)	(BMAP_CHUNK_NO(p) * BMAP_CHUNK_BITS)
91 
92 
93 /*
94  * Bitmap flags.
95  */
96 #define	BMAP_BINIT_ONES	0x00000001 /* initial value of bits is 1 */
97 #define	BMAP_INUSE	0x00000002 /* slot is in use */
98 
99 
100 /*
101  * Macros of bitmap flags.
102  */
103 #define	BMAP_SET_FLAGS(b, f)	((b)->bm_flags |= (f))
104 #define	BMAP_UNSET_FLAGS(b, f)	((b)->bm_flags &= ~(f))
105 
106 #define	BMAP_IS_INIT_ONES(b)	((b)->bm_flags & BMAP_BINIT_ONES)
107 #define	BMAP_IS_INUSE(b)	((b)->bm_flags & BMAP_INUSE)
108 
109 
110 #define	HASH(p)		(((p) / BMAP_CHUNK_BITS) % BMAP_HASH_SIZE)
111 
112 /*
113  * Calculate the memory size in bytes needed for the specified length
114  * of bitmap.
115  */
116 #define	ROUNDUP(n, d)	(((n) + (d) - 1) / (d))
117 #define	MEM_LEN(l)	(ROUNDUP((l), BMAP_BPW) * BMAP_WSIZE)
118 
119 
120 /*
121  * Chunk flags.
122  */
123 #define	BMAP_CSET_DIRTY(cp)	(cp)->c_flags |= BMAP_CDIRTY
124 #define	BMAP_CDIRTY	0x00000001 /* the chunk is dirty */
125 
126 
127 /*
128  * Macros on chunk flags.
129  */
130 #define	BMAP_CIS_DIRTY(cp)	((cp)->c_flags & BMAP_CDIRTY)
131 
132 
133 /*
134  * When loading a bitmap chunk, if it is new set the bitmap
135  * can be set according to the initial value of bits.
136  * Otherwise, it should be loaded from the file.
137  */
138 #define	BMAP_NEW_CHUNK		1
139 #define	BMAP_OLD_CHUNK		0
140 
141 /*
142  * Each chunk holds the followin information:
143  *  - A flag showing the status of the chunk, like being ditry or not.
144  *  - Its offset in bits from the beginning of the vector.
145  *  - Its length in bits.
146  *  - Its memory length in use in bytes.
147  *  - The bitmap vector.
148  *
149  *  In addition to the above information, each chunk can be on two lists:
150  *  one the hash list, the other LRU list.  The hash list is a MRU list,
151  *  meaning the MRU entry is at the head of the list.
152  *
153  *  All the chunks are in the LRU list. When a chunk is needed and there is
154  *  no more room for allocating chunks, the first entry of this list is
155  *  reclaimed.
156  */
157 typedef struct dbmap_chunk {
158 	TAILQ_ENTRY(dbmap_chunk) c_hash;
159 	TAILQ_ENTRY(dbmap_chunk) c_lru;
160 	uint_t c_flags;
161 	u_quad_t c_off;
162 	uint_t c_clen;
163 	uint_t c_mlen;
164 	uint_t *c_bmp;
165 } dbmap_chunk_t;
166 
167 
168 TAILQ_HEAD(dbmap_list, dbmap_chunk);
169 typedef struct dbmap_list dbmap_list_t;
170 
171 
172 typedef struct dbitmap {
173 	char *bm_fname;
174 	int bm_fd;
175 	uint_t bm_flags;
176 	u_quad_t bm_len; /* bitmap length */
177 	uint_t bm_cmax; /* maximum number of cached chunks */
178 	uint_t bm_ccur; /* current number of cached chunks */
179 	dbmap_list_t bm_hash[BMAP_HASH_SIZE]; /* MRU hash table */
180 	dbmap_list_t bm_lru; /* LRU list */
181 } dbitmap_t;
182 
183 /*
184  * Disk bitmap table.  Upon allocating a dbitmap, one slot
185  * of this table will be used.
186  */
187 static dbitmap_t dbitmap[BMAP_MAX];
188 
189 
190 /*
191  * Each chunk holds the followin information:
192  *  - Its offset in bits from the beginning of the vector.
193  *  - Its length in bits.
194  *  - Its memory length in use in bytes.
195  *  - The bitmap vector.
196  *
197  *  In addition to the above information, each chunk can be on a list:
198  *  one the hash list.  The hash list is a MRU list,  meaning that the
199  *  MRU entry is at the head of the list.
200  */
201 typedef struct bmap_chunk {
202 	TAILQ_ENTRY(bmap_chunk) c_hash;
203 	u_quad_t c_off;
204 	uint_t c_clen;
205 	uint_t c_mlen;
206 	uint_t *c_bmp;
207 } bmap_chunk_t;
208 
209 
210 TAILQ_HEAD(bmap_list, bmap_chunk);
211 typedef struct bmap_list bmap_list_t;
212 
213 
214 typedef struct bitmap {
215 	uint_t bm_flags;
216 	u_quad_t bm_len; /* bitmap length */
217 	uint_t bm_cmax; /* maximum number of cached chunks */
218 	uint_t bm_ccur; /* current number of cached chunks */
219 	bmap_list_t bm_hash[BMAP_HASH_SIZE]; /* MRU hash table */
220 } bitmap_t;
221 
222 
223 /*
224  * Statistics gathering structure.
225  */
226 typedef struct bitmap_stats {
227 	ulong_t bs_alloc_cnt;
228 	ulong_t bs_alloc_size;
229 	ulong_t bs_free_cnt;
230 	ulong_t bs_set_applied;
231 	ulong_t bs_unset_applied;
232 	ulong_t bs_cache_hit;
233 	ulong_t bs_cache_miss;
234 	ulong_t bs_chunk_new;
235 	ulong_t bs_chunk_flush;
236 	ulong_t bs_chunk_reclaim;
237 	u_quad_t bs_get;
238 	u_quad_t bs_get_bits;
239 	u_quad_t bs_set;
240 	u_quad_t bs_set_bits;
241 	u_quad_t bs_unset;
242 	u_quad_t bs_unset_bits;
243 } bitmap_stats_t;
244 
245 
246 /*
247  * Disk bitmap table.  Upon allocating a bitmap, one slot
248  * of this table will be used.
249  */
250 static bitmap_t bitmap[BMAP_MAX];
251 
252 
253 /*
254  * Global instance of statistics variable.
255  */
256 bitmap_stats_t bitmap_stats;
257 
258 
259 /*
260  * bmd2bmp
261  *
262  * Convert bitmap descriptor to bitmap pointer.
263  */
264 static bitmap_t *
bmd2bmp(int bmd)265 bmd2bmp(int bmd)
266 {
267 	if (bmd < 0 || bmd >= BMAP_MAX)
268 		return (NULL);
269 
270 	return (&bitmap[bmd]);
271 }
272 
273 
274 /*
275  * bmd_alloc
276  *
277  * Allocate a bitmap descriptor.  Sets the INUSE flag of the slot.
278  */
279 static int
bmd_alloc(void)280 bmd_alloc(void)
281 {
282 	int i;
283 	bitmap_t *bmp;
284 
285 	bmp = bitmap;
286 	for (i = 0; i < BMAP_MAX; bmp++, i++)
287 		if (!BMAP_IS_INUSE(bmp)) {
288 			BMAP_SET_FLAGS(bmp, BMAP_INUSE);
289 			return (i);
290 		}
291 
292 	return (-1);
293 }
294 
295 
296 /*
297  * bmd_free
298  *
299  * Free a bitmap descriptor.  Clears the INUSE flag of the slot.
300  */
301 static void
bmd_free(int bmd)302 bmd_free(int bmd)
303 {
304 	bitmap_t *bmp;
305 
306 	bmp = bmd2bmp(bmd);
307 	if (bmp)
308 		BMAP_UNSET_FLAGS(bmp, BMAP_INUSE);
309 }
310 
311 
312 /*
313  * bmp_set
314  *
315  * Generic function to set bit in a chunk.  This can set or unset the
316  * specified bit.
317  */
318 static inline int
bmp_set(bmap_chunk_t * cp,u_quad_t bn,uint_t * vp)319 bmp_set(bmap_chunk_t *cp, u_quad_t bn, uint_t *vp)
320 {
321 	int rv;
322 	uint_t mask;
323 	uint_t *ip;
324 	uint_t v;
325 
326 	bn -= cp->c_off;
327 	if (bn < cp->c_clen) {
328 		mask = 1 <<(bn & BMAP_BPW_MASK);
329 		ip = &cp->c_bmp[bn >> BMAP_BPW_SHIFT];
330 		v = (*vp <<(bn & BMAP_BPW_MASK)) & mask;
331 		*ip = (*ip & ~mask) | v;
332 		rv = 0;
333 	} else
334 		rv = -ERANGE;
335 
336 	return (rv);
337 }
338 
339 
340 /*
341  * bmp_get
342  *
343  * Generic function to get bit in a chunk.
344  */
345 static inline int
bmp_get(bmap_chunk_t * cp,u_quad_t bn)346 bmp_get(bmap_chunk_t *cp, u_quad_t bn)
347 {
348 	int rv;
349 	uint_t bit;
350 
351 	bn -= cp->c_off;
352 	if (bn < cp->c_clen) {
353 		bit = 1 <<(bn & BMAP_BPW_MASK);
354 		rv = (cp->c_bmp[bn >> BMAP_BPW_SHIFT] & bit) != 0;
355 	} else
356 		rv = -ERANGE;
357 
358 	return (rv);
359 }
360 
361 
362 /*
363  * bm_chuck_setup
364  *
365  * Set up the properties of the new chunk and position it in the hash list.
366  */
367 static bmap_chunk_t *
bm_chunk_setup(bitmap_t * bmp,bmap_chunk_t * cp,u_quad_t bn)368 bm_chunk_setup(bitmap_t *bmp, bmap_chunk_t *cp, u_quad_t bn)
369 {
370 	int h;
371 	u_quad_t off, l;
372 	uint_t cl, ml;
373 	bmap_list_t *hp;
374 
375 	off = BMAP_CHUNK_OFF(bn);
376 	l = bmp->bm_len - off;
377 	if (l >= BMAP_CHUNK_BITS) {
378 		cl = BMAP_CHUNK_BITS;
379 		ml = BMAP_CHUNK_BYTES;
380 	} else {
381 		cl = l;
382 		ml = MEM_LEN(l);
383 	}
384 
385 	if (BMAP_IS_INIT_ONES(bmp))
386 		(void) memset(cp->c_bmp, 0xff, ml);
387 	else
388 		(void) memset(cp->c_bmp, 0x00, ml);
389 
390 	h = HASH(bn);
391 	hp = &bmp->bm_hash[h];
392 
393 	TAILQ_INSERT_HEAD(hp, cp, c_hash);
394 	cp->c_off = off;
395 	cp->c_clen = cl;
396 	cp->c_mlen = ml;
397 	return (cp);
398 }
399 
400 
401 /*
402  * bm_chunk_new
403  *
404  * Create a new chunk and keep track of memory used.
405  */
406 static bmap_chunk_t *
bm_chunk_new(bitmap_t * bmp,u_quad_t bn)407 bm_chunk_new(bitmap_t *bmp, u_quad_t bn)
408 {
409 	bmap_chunk_t *cp;
410 
411 	bitmap_stats.bs_chunk_new++;
412 
413 	cp = ndmp_malloc(sizeof (bmap_chunk_t));
414 	if (cp) {
415 		cp->c_bmp = ndmp_malloc(sizeof (uint_t) * BMAP_CHUNK_WORDS);
416 		if (!cp->c_bmp) {
417 			free(cp);
418 			cp = NULL;
419 		} else {
420 			(void) bm_chunk_setup(bmp, cp, bn);
421 			bmp->bm_ccur++;
422 		}
423 	}
424 
425 	return (cp);
426 }
427 
428 
429 /*
430  * bm_chunk_alloc
431  *
432  * Allocate a chunk and return it.  If the cache for the chunks is not
433  * fully used, a new chunk is created.
434  */
435 static bmap_chunk_t *
bm_chunk_alloc(bitmap_t * bmp,u_quad_t bn)436 bm_chunk_alloc(bitmap_t *bmp, u_quad_t bn)
437 {
438 	bmap_chunk_t *cp;
439 
440 	if (bmp->bm_ccur < bmp->bm_cmax)
441 		cp = bm_chunk_new(bmp, bn);
442 	else
443 		cp = NULL;
444 
445 	return (cp);
446 }
447 
448 
449 /*
450  * hash_free
451  *
452  * Free all chunks on the hash list.
453  */
454 void
hash_free(bmap_list_t * hp)455 hash_free(bmap_list_t *hp)
456 {
457 	bmap_chunk_t *cp;
458 
459 	if (!hp)
460 		return;
461 
462 	while (!TAILQ_EMPTY(hp)) {
463 		cp = TAILQ_FIRST(hp);
464 		TAILQ_REMOVE(hp, cp, c_hash);
465 		free(cp->c_bmp);
466 		free(cp);
467 	}
468 }
469 
470 
471 /*
472  * bm_chunks_free
473  *
474  * Release the memory allocated for the chunks.
475  */
476 static void
bm_chunks_free(bmap_list_t * hp)477 bm_chunks_free(bmap_list_t *hp)
478 {
479 	int i;
480 
481 	for (i = 0; i < BMAP_HASH_SIZE; hp++, i++)
482 		hash_free(hp);
483 }
484 
485 
486 /*
487  * bm_chunk_repositions
488  *
489  * Re-position the chunk in the MRU hash table.
490  */
491 static void
bm_chunk_reposition(bitmap_t * bmp,bmap_list_t * hp,bmap_chunk_t * cp)492 bm_chunk_reposition(bitmap_t *bmp, bmap_list_t *hp, bmap_chunk_t *cp)
493 {
494 	if (!bmp || !hp || !cp)
495 		return;
496 
497 	if (TAILQ_FIRST(hp) != cp) {
498 		TAILQ_REMOVE(hp, cp, c_hash);
499 		TAILQ_INSERT_HEAD(hp, cp, c_hash);
500 	}
501 }
502 
503 
504 /*
505  * bm_chunk_find
506  *
507  * Find and return the chunks which holds the specified bit. Allocate
508  * the chunk if necessary and re-position it in the hash table lists.
509  */
510 static bmap_chunk_t *
bm_chunk_find(bitmap_t * bmp,u_quad_t bn)511 bm_chunk_find(bitmap_t *bmp, u_quad_t bn)
512 {
513 	int h;
514 	bmap_chunk_t *cp;
515 	bmap_list_t *hp;
516 
517 	if (!bmp)
518 		return (NULL);
519 
520 	h = HASH(bn);
521 	hp = &bmp->bm_hash[h];
522 	TAILQ_FOREACH(cp, hp, c_hash) {
523 		if (bn >= cp->c_off && bn < (cp->c_off + cp->c_clen)) {
524 			bitmap_stats.bs_cache_hit++;
525 
526 			bm_chunk_reposition(bmp, hp, cp);
527 			return (cp);
528 		}
529 	}
530 
531 	bitmap_stats.bs_cache_miss++;
532 
533 	return (bm_chunk_alloc(bmp, bn));
534 }
535 
536 
537 /*
538  * bmp_setval
539  *
540  * Set a range of bits in the bitmap specified by the vector.
541  */
542 static int
bmp_setval(bitmap_t * bmp,bm_iovec_t * vp)543 bmp_setval(bitmap_t *bmp, bm_iovec_t *vp)
544 {
545 	int rv;
546 	u_quad_t cl;
547 	u_quad_t bn;
548 	u_quad_t max;
549 	bmap_chunk_t *cp;
550 
551 	bn = vp->bmv_base;
552 	max = bn + vp->bmv_len;
553 	if (bn >= bmp->bm_len || max > bmp->bm_len)
554 		return (-EINVAL);
555 
556 	if (*vp->bmv_val) {
557 		bitmap_stats.bs_set++;
558 		bitmap_stats.bs_set_bits += vp->bmv_len;
559 	} else {
560 		bitmap_stats.bs_unset++;
561 		bitmap_stats.bs_unset_bits += vp->bmv_len;
562 	}
563 
564 	do {
565 		cp = bm_chunk_find(bmp, bn);
566 		if (!cp)
567 			return (-ERANGE);
568 
569 		for (cl = cp->c_off + cp->c_clen; bn < cl && bn < max; bn++) {
570 			rv = bmp_set(cp, bn, vp->bmv_val);
571 			if (rv != 0)
572 				return (rv);
573 		}
574 	} while (bn < max);
575 
576 	return (0);
577 }
578 
579 
580 /*
581  * bmp_getval
582  *
583  * Get a range of bits in the bitmap specified by the vector.
584  */
585 static int
bmp_getval(bitmap_t * bmp,bm_iovec_t * vp)586 bmp_getval(bitmap_t *bmp, bm_iovec_t *vp)
587 {
588 	uint_t cnt;
589 	uint_t *ip;
590 	int rv;
591 	u_quad_t cl;
592 	u_quad_t bn;
593 	u_quad_t max;
594 	bmap_chunk_t *cp;
595 
596 	bn = vp->bmv_base;
597 	max = bn + vp->bmv_len;
598 	if (bn >= bmp->bm_len || max > bmp->bm_len)
599 		return (-EINVAL);
600 
601 	bitmap_stats.bs_get++;
602 	bitmap_stats.bs_get_bits += 1;
603 
604 	cnt = 0;
605 	ip = vp->bmv_val;
606 	*ip = 0;
607 	do {
608 		cp = bm_chunk_find(bmp, bn);
609 		if (!cp)
610 			return (-ERANGE);
611 
612 		for (cl = cp->c_off + cp->c_clen; bn < cl && bn < max; bn++) {
613 			rv = bmp_get(cp, bn);
614 			if (rv < 0)
615 				return (rv);
616 
617 			*ip |= rv << cnt;
618 			if (++cnt >= BMAP_BPW) {
619 				*++ip = 0;
620 				cnt = 0;
621 			}
622 		}
623 	} while (bn < max);
624 
625 	return (0);
626 }
627 
628 
629 /*
630  * hash_init
631  *
632  * Initialize the hash table lists head.
633  */
634 static void
hash_init(bmap_list_t * hp)635 hash_init(bmap_list_t *hp)
636 {
637 	int i;
638 
639 	for (i = 0; i < BMAP_HASH_SIZE; hp++, i++) {
640 		TAILQ_INIT(hp);
641 	}
642 }
643 
644 
645 /*
646  * bm_alloc
647  *
648  * Allocate a bit map and return a handle to it.
649  *
650  * The hash table list are empty at this point. They are allocated
651  * on demand.
652  */
653 int
bm_alloc(u_quad_t len,int set)654 bm_alloc(u_quad_t len, int set)
655 {
656 	int bmd;
657 	bitmap_t *bmp;
658 
659 	if (len == 0)
660 		return (-1);
661 
662 	bmd = bmd_alloc();
663 	if (bmd < 0)
664 		return (bmd);
665 
666 	bmp = bmd2bmp(bmd);
667 	bitmap_stats.bs_alloc_cnt++;
668 	bitmap_stats.bs_alloc_size += len;
669 
670 	if (set)
671 		BMAP_SET_FLAGS(bmp, BMAP_BINIT_ONES);
672 	else
673 		BMAP_UNSET_FLAGS(bmp, BMAP_BINIT_ONES);
674 	bmp->bm_len = len;
675 	bmp->bm_ccur = 0;
676 	bmp->bm_cmax = BMAP_CHUNK_MAX;
677 	hash_init(bmp->bm_hash);
678 
679 	return (bmd);
680 }
681 
682 
683 /*
684  * bm_free
685  *
686  * Free memory allocated for the bitmap.
687  */
688 int
bm_free(int bmd)689 bm_free(int bmd)
690 {
691 	int rv;
692 	bitmap_t *bmp;
693 
694 	bmp = bmd2bmp(bmd);
695 	if (bmp && BMAP_IS_INUSE(bmp)) {
696 		bitmap_stats.bs_free_cnt++;
697 
698 		bm_chunks_free(bmp->bm_hash);
699 		bmd_free(bmd);
700 		rv = 0;
701 	} else
702 		rv = -1;
703 
704 	return (rv);
705 }
706 
707 
708 /*
709  * bm_getiov
710  *
711  * Get bits specified by the array of vectors.
712  */
713 int
bm_getiov(int bmd,bm_io_t * iop)714 bm_getiov(int bmd, bm_io_t *iop)
715 {
716 	int i;
717 	int rv;
718 	bm_iovec_t *vp;
719 	bitmap_t *bmp;
720 
721 	if (!iop)
722 		rv = -EINVAL;
723 	else if (!(bmp = bmd2bmp(bmd)))
724 		rv = -EINVAL;
725 	else if (iop->bmio_iovcnt <= 0)
726 		rv = -EINVAL;
727 	else {
728 		rv = 0;
729 		vp = iop->bmio_iov;
730 		for (i = 0; i < iop->bmio_iovcnt; vp++, i++) {
731 			if (!vp)
732 				return (-EINVAL);
733 			rv |= bmp_getval(bmp, vp);
734 		}
735 	}
736 
737 	return (rv);
738 }
739 
740 
741 /*
742  * bm_setiov
743  *
744  * Set bits specified by the array of vectors.
745  */
746 int
bm_setiov(int bmd,bm_io_t * iop)747 bm_setiov(int bmd, bm_io_t *iop)
748 {
749 	int i;
750 	int rv;
751 	bm_iovec_t *vp;
752 	bitmap_t *bmp;
753 
754 	if (!iop)
755 		rv = -EINVAL;
756 	else if (!(bmp = bmd2bmp(bmd)))
757 		rv = -EINVAL;
758 	else if (iop->bmio_iovcnt <= 0)
759 		rv = -EINVAL;
760 	else if (!iop->bmio_iov)
761 		rv = -EINVAL;
762 	else {
763 		rv = 0;
764 		vp = iop->bmio_iov;
765 		for (i = 0; i < iop->bmio_iovcnt; vp++, i++)
766 			rv |= bmp_setval(bmp, vp);
767 	}
768 
769 	return (rv);
770 }
771 
772 
773 /*
774  * bmd2dbmp
775  *
776  * Convert bitmap descriptor to bitmap pointer.
777  */
778 static dbitmap_t *
bmd2dbmp(int bmd)779 bmd2dbmp(int bmd)
780 {
781 	if (bmd < 0 || bmd >= BMAP_MAX)
782 		return (NULL);
783 
784 	return (&dbitmap[bmd]);
785 }
786 
787 
788 /*
789  * dbmp2bmd
790  *
791  * Convert bitmap pointer to bitmap descriptor.
792  */
793 static int
dbmp2bmd(dbitmap_t * bmp)794 dbmp2bmd(dbitmap_t *bmp)
795 {
796 	int bmd;
797 
798 	bmd = bmp - dbitmap;
799 	if (bmd < 0 || bmd >= BMAP_MAX)
800 		bmd = -1;
801 
802 	return (bmd);
803 }
804 
805 /*
806  * dbmd_alloc
807  *
808  * Allocate a bitmap descriptor.
809  * Sets the INUSE flag of the slot.
810  */
811 static int
dbmd_alloc(void)812 dbmd_alloc(void)
813 {
814 	int i;
815 	dbitmap_t *bmp;
816 
817 	bmp = dbitmap;
818 	for (i = 0; i < BMAP_MAX; bmp++, i++)
819 		if (!BMAP_IS_INUSE(bmp)) {
820 			BMAP_SET_FLAGS(bmp, BMAP_INUSE);
821 			return (i);
822 		}
823 
824 	return (-1);
825 }
826 
827 
828 /*
829  * dbmd_free
830  *
831  * Free a bitmap descriptor.
832  * Clears the INUSE flag of the slot.
833  */
834 static void
dbmd_free(int bmd)835 dbmd_free(int bmd)
836 {
837 	dbitmap_t *bmp;
838 
839 	bmp = bmd2dbmp(bmd);
840 	if (bmp)
841 		BMAP_UNSET_FLAGS(bmp, BMAP_INUSE);
842 }
843 
844 
845 /*
846  * dbmp_set
847  *
848  * Generic function to set bit in a chunk.  This can
849  * set or unset the specified bit.
850  */
851 static inline int
dbmp_set(dbmap_chunk_t * cp,u_quad_t bn,uint_t * vp)852 dbmp_set(dbmap_chunk_t *cp, u_quad_t bn, uint_t *vp)
853 {
854 	int rv;
855 	uint_t mask;
856 	uint_t *ip;
857 	uint_t v;
858 
859 	bn -= cp->c_off;
860 	if (bn < cp->c_clen) {
861 		mask = 1 <<(bn & BMAP_BPW_MASK);
862 		ip = &cp->c_bmp[bn >> BMAP_BPW_SHIFT];
863 		v = (*vp <<(bn & BMAP_BPW_MASK)) & mask;
864 		*ip = (*ip & ~mask) | v;
865 		BMAP_CSET_DIRTY(cp);
866 		rv = 0;
867 	} else
868 		rv = -ERANGE;
869 
870 	return (rv);
871 }
872 
873 
874 /*
875  * dbmp_getlen
876  *
877  * Get length of the bitmap.
878  */
879 static u_quad_t
dbmp_getlen(dbitmap_t * bmp)880 dbmp_getlen(dbitmap_t *bmp)
881 {
882 	return (bmp ? bmp->bm_len : 0LL);
883 }
884 
885 
886 /*
887  * dbmp_get
888  *
889  * Generic function to get bit in a chunk.
890  */
891 static inline int
dbmp_get(dbmap_chunk_t * cp,u_quad_t bn)892 dbmp_get(dbmap_chunk_t *cp, u_quad_t bn)
893 {
894 	int rv;
895 	uint_t bit;
896 
897 	bn -= cp->c_off;
898 	if (bn < cp->c_clen) {
899 		bit = 1 <<(bn & BMAP_BPW_MASK);
900 		rv = (cp->c_bmp[bn >> BMAP_BPW_SHIFT] & bit) != 0;
901 	} else
902 		rv = -ERANGE;
903 
904 	return (rv);
905 }
906 
907 
908 /*
909  * dbm_chunk_seek
910  *
911  * Seek in the file where the chunk is saved or should be saved.
912  */
913 static int
dbm_chunk_seek(dbitmap_t * bmp,u_quad_t bn)914 dbm_chunk_seek(dbitmap_t *bmp, u_quad_t bn)
915 {
916 	int rv;
917 	off_t off;
918 
919 	if (!bmp)
920 		rv = -1;
921 	else {
922 		off = BMAP_CHUNK_NO(bn) * BMAP_CHUNK_BYTES;
923 		rv = (lseek(bmp->bm_fd, off, SEEK_SET) != off) ? -1 : 0;
924 	}
925 
926 	return (rv);
927 }
928 
929 
930 /*
931  * dbm_chunk_flush
932  *
933  * Save a chunk to file.
934  */
935 static int
dbm_chunk_flush(dbitmap_t * bmp,dbmap_chunk_t * cp)936 dbm_chunk_flush(dbitmap_t *bmp, dbmap_chunk_t *cp)
937 {
938 	int rv;
939 
940 	bitmap_stats.bs_chunk_flush++;
941 	if (!bmp || !cp)
942 		rv = -1;
943 	else if (dbm_chunk_seek(bmp, cp->c_off) != 0)
944 		rv = -1;
945 	else if (write(bmp->bm_fd, cp->c_bmp, cp->c_mlen) != cp->c_mlen)
946 		rv = -1;
947 	else
948 		rv = 0;
949 
950 	return (rv);
951 }
952 
953 
954 /*
955  * dbm_chunk_load
956  *
957  * Load a chunk from a file.  If the chunk is a new one,
958  * instead of reading from the disk, the memory for the
959  * chunk is set to either all zeros or to all ones.
960  * Otherwise, if the chunk is not a new one, it's read
961  * from the disk.
962  *
963  * The new chunk is positioned in the LRU and hash table
964  * after its data is ready.
965  */
966 static dbmap_chunk_t *
dbm_chunk_load(dbitmap_t * bmp,dbmap_chunk_t * cp,u_quad_t bn,int new)967 dbm_chunk_load(dbitmap_t *bmp, dbmap_chunk_t *cp, u_quad_t bn, int new)
968 {
969 	int h;
970 	u_quad_t off, l;
971 	uint_t cl, ml;
972 	dbmap_list_t *hp;
973 
974 	off = BMAP_CHUNK_OFF(bn);
975 	l = bmp->bm_len - off;
976 	if (l >= BMAP_CHUNK_BITS) {
977 		cl = BMAP_CHUNK_BITS;
978 		ml = BMAP_CHUNK_BYTES;
979 	} else {
980 		cl = l;
981 		ml = MEM_LEN(l);
982 	}
983 
984 	if (new == BMAP_NEW_CHUNK) {
985 		if (BMAP_IS_INIT_ONES(bmp))
986 			(void) memset(cp->c_bmp, 0xff, ml);
987 		else
988 			(void) memset(cp->c_bmp, 0x00, ml);
989 	} else { /* BMAP_OLD_CHUNK */
990 		if (dbm_chunk_seek(bmp, bn) != 0)
991 			cp = NULL;
992 		else if (read(bmp->bm_fd, cp->c_bmp, ml) != ml)
993 			cp = NULL;
994 	}
995 
996 	if (cp) {
997 		TAILQ_INSERT_TAIL(&bmp->bm_lru, cp, c_lru);
998 		h = HASH(bn);
999 		hp = &bmp->bm_hash[h];
1000 		TAILQ_INSERT_HEAD(hp, cp, c_hash);
1001 		cp->c_flags = 0;
1002 		cp->c_off = off;
1003 		cp->c_clen = cl;
1004 		cp->c_mlen = ml;
1005 	}
1006 
1007 	return (cp);
1008 }
1009 
1010 
1011 /*
1012  * dbm_chunk_new
1013  *
1014  * Create a new chunk and keep track of memory used.
1015  */
1016 static dbmap_chunk_t *
dbm_chunk_new(dbitmap_t * bmp,u_quad_t bn)1017 dbm_chunk_new(dbitmap_t *bmp, u_quad_t bn)
1018 {
1019 	dbmap_chunk_t *cp;
1020 
1021 	bitmap_stats.bs_chunk_new++;
1022 	cp = ndmp_malloc(sizeof (dbmap_chunk_t));
1023 	if (cp) {
1024 		cp->c_bmp = ndmp_malloc(sizeof (uint_t) * BMAP_CHUNK_WORDS);
1025 		if (!cp->c_bmp) {
1026 			free(cp);
1027 			cp = NULL;
1028 		} else if (!dbm_chunk_load(bmp, cp, bn, BMAP_NEW_CHUNK)) {
1029 			free(cp->c_bmp);
1030 			free(cp);
1031 			cp = NULL;
1032 		} else
1033 			bmp->bm_ccur++;
1034 	}
1035 
1036 	return (cp);
1037 }
1038 
1039 
1040 /*
1041  * dbm_chunk_alloc
1042  *
1043  * Allocate a chunk and return it.  If the cache for the
1044  * chunks is not fully used, a new chunk is created.
1045  * Otherwise, the first chunk from the LRU list is reclaimed,
1046  * loaded and returned.
1047  */
1048 static dbmap_chunk_t *
dbm_chunk_alloc(dbitmap_t * bmp,u_quad_t bn)1049 dbm_chunk_alloc(dbitmap_t *bmp, u_quad_t bn)
1050 {
1051 	int h;
1052 	dbmap_list_t *hp;
1053 	dbmap_chunk_t *cp;
1054 
1055 	if (bmp->bm_ccur < bmp->bm_cmax)
1056 		return (dbm_chunk_new(bmp, bn));
1057 
1058 	bitmap_stats.bs_chunk_reclaim++;
1059 
1060 	cp = TAILQ_FIRST(&bmp->bm_lru);
1061 	if (BMAP_CIS_DIRTY(cp))
1062 		(void) dbm_chunk_flush(bmp, cp);
1063 
1064 	TAILQ_REMOVE(&bmp->bm_lru, cp, c_lru);
1065 	h = HASH(cp->c_off);
1066 	hp = &bmp->bm_hash[h];
1067 	TAILQ_REMOVE(hp, cp, c_hash);
1068 	return (dbm_chunk_load(bmp, cp, bn, BMAP_OLD_CHUNK));
1069 }
1070 
1071 
1072 /*
1073  * dbm_chunks_free
1074  *
1075  * Release the memory allocated for the chunks.
1076  */
1077 static void
dbm_chunks_free(dbitmap_t * bmp)1078 dbm_chunks_free(dbitmap_t *bmp)
1079 {
1080 	dbmap_list_t *headp;
1081 	dbmap_chunk_t *cp;
1082 
1083 	if (!bmp)
1084 		return;
1085 
1086 	headp = &bmp->bm_lru;
1087 	if (!headp)
1088 		return;
1089 
1090 	while (!TAILQ_EMPTY(headp)) {
1091 		cp = TAILQ_FIRST(headp);
1092 		TAILQ_REMOVE(headp, cp, c_lru);
1093 		free(cp->c_bmp);
1094 		free(cp);
1095 	}
1096 }
1097 
1098 
1099 /*
1100  * dbm_chunk_reposition
1101  *
1102  * Re-position the chunk in the LRU and the hash table.
1103  */
1104 static void
dbm_chunk_reposition(dbitmap_t * bmp,dbmap_list_t * hp,dbmap_chunk_t * cp)1105 dbm_chunk_reposition(dbitmap_t *bmp, dbmap_list_t *hp, dbmap_chunk_t *cp)
1106 {
1107 	if (bmp && hp && cp) {
1108 		TAILQ_REMOVE(&bmp->bm_lru, cp, c_lru);
1109 		TAILQ_INSERT_TAIL(&bmp->bm_lru, cp, c_lru);
1110 		if (TAILQ_FIRST(hp) != cp) {
1111 			TAILQ_REMOVE(hp, cp, c_hash);
1112 			TAILQ_INSERT_HEAD(hp, cp, c_hash);
1113 		}
1114 	}
1115 }
1116 
1117 
1118 /*
1119  * dbm_chunk_find
1120  *
1121  * Find and return the chunks which holds the specified bit.
1122  * Allocate the chunk if necessary and re-position it in the
1123  * LRU and hash table lists.
1124  */
1125 static dbmap_chunk_t *
dbm_chunk_find(dbitmap_t * bmp,u_quad_t bn)1126 dbm_chunk_find(dbitmap_t *bmp, u_quad_t bn)
1127 {
1128 	int h;
1129 	dbmap_chunk_t *cp;
1130 	dbmap_list_t *hp;
1131 
1132 	if (!bmp)
1133 		return (NULL);
1134 
1135 	h = HASH(bn);
1136 	hp = &bmp->bm_hash[h];
1137 	TAILQ_FOREACH(cp, hp, c_hash) {
1138 		if (bn >= cp->c_off && bn < (cp->c_off + cp->c_clen)) {
1139 			bitmap_stats.bs_cache_hit++;
1140 
1141 			dbm_chunk_reposition(bmp, hp, cp);
1142 			return (cp);
1143 		}
1144 	}
1145 
1146 	bitmap_stats.bs_cache_miss++;
1147 
1148 	return (dbm_chunk_alloc(bmp, bn));
1149 }
1150 
1151 
1152 /*
1153  * dbmp_setval
1154  *
1155  * Set a range of bits in the bitmap specified by the
1156  * vector.
1157  */
1158 static int
dbmp_setval(dbitmap_t * bmp,bm_iovec_t * vp)1159 dbmp_setval(dbitmap_t *bmp, bm_iovec_t *vp)
1160 {
1161 	int rv;
1162 	u_quad_t cl;
1163 	u_quad_t bn;
1164 	u_quad_t max;
1165 	dbmap_chunk_t *cp;
1166 
1167 	bn = vp->bmv_base;
1168 	max = bn + vp->bmv_len;
1169 	if (bn >= bmp->bm_len || max > bmp->bm_len)
1170 		return (-EINVAL);
1171 
1172 	if (*vp->bmv_val) {
1173 		bitmap_stats.bs_set++;
1174 		bitmap_stats.bs_set_bits += vp->bmv_len;
1175 	} else {
1176 		bitmap_stats.bs_unset++;
1177 		bitmap_stats.bs_unset_bits += vp->bmv_len;
1178 	}
1179 
1180 	do {
1181 		cp = dbm_chunk_find(bmp, bn);
1182 		if (!cp)
1183 			return (-ERANGE);
1184 
1185 		for (cl = cp->c_off + cp->c_clen; bn < cl && bn < max; bn++) {
1186 			rv = dbmp_set(cp, bn, vp->bmv_val);
1187 			if (rv != 0)
1188 				return (rv);
1189 		}
1190 	} while (bn < max);
1191 
1192 	return (0);
1193 }
1194 
1195 
1196 /*
1197  * dbmp_getval
1198  *
1199  * Get a range of bits in the bitmap specified by the
1200  * vector.
1201  */
1202 static int
dbmp_getval(dbitmap_t * bmp,bm_iovec_t * vp)1203 dbmp_getval(dbitmap_t *bmp, bm_iovec_t *vp)
1204 {
1205 	uint_t cnt;
1206 	uint_t *ip;
1207 	int rv;
1208 	u_quad_t cl;
1209 	u_quad_t bn;
1210 	u_quad_t max;
1211 	dbmap_chunk_t *cp;
1212 
1213 	bn = vp->bmv_base;
1214 	max = bn + vp->bmv_len;
1215 	if (bn >= bmp->bm_len || max > bmp->bm_len)
1216 		return (-EINVAL);
1217 
1218 	bitmap_stats.bs_get++;
1219 	bitmap_stats.bs_get_bits += 1;
1220 
1221 	cnt = 0;
1222 	ip = vp->bmv_val;
1223 	*ip = 0;
1224 	do {
1225 		cp = dbm_chunk_find(bmp, bn);
1226 		if (!cp)
1227 			return (-ERANGE);
1228 
1229 		for (cl = cp->c_off + cp->c_clen; bn < cl && bn < max; bn++) {
1230 			rv = dbmp_get(cp, bn);
1231 			if (rv < 0)
1232 				return (rv);
1233 
1234 			*ip |= rv << cnt;
1235 			if (++cnt >= BMAP_BPW) {
1236 				*++ip = 0;
1237 				cnt = 0;
1238 			}
1239 		}
1240 	} while (bn < max);
1241 
1242 	return (0);
1243 }
1244 
1245 
1246 /*
1247  * dbyte_apply_ifset
1248  *
1249  * Apply the function on the set bits of the specified word.
1250  */
1251 static int
dbyte_apply_ifset(dbitmap_t * bmp,u_quad_t off,uint_t b,int (* fp)(),void * arg)1252 dbyte_apply_ifset(dbitmap_t *bmp, u_quad_t off, uint_t b, int(*fp)(),
1253     void *arg)
1254 {
1255 	int bmd;
1256 	int rv;
1257 	u_quad_t l;
1258 
1259 	rv = 0;
1260 	l = dbmp_getlen(bmp);
1261 	bmd = dbmp2bmd(bmp);
1262 	for (; b && off < l; off++) {
1263 		if (b & 1) {
1264 			bitmap_stats.bs_set_applied++;
1265 
1266 			if ((rv = (*fp)(bmd, off, arg)))
1267 				break;
1268 		}
1269 		b >>= 1;
1270 	}
1271 
1272 	return (rv);
1273 }
1274 
1275 
1276 /*
1277  * dbm_chunk_apply_ifset
1278  *
1279  * Apply the function on the set bits of the specified chunk.
1280  */
1281 static int
dbm_chunk_apply_ifset(dbitmap_t * bmp,dbmap_chunk_t * cp,int (* fp)(),void * arg)1282 dbm_chunk_apply_ifset(dbitmap_t *bmp, dbmap_chunk_t *cp, int(*fp)(),
1283     void *arg)
1284 {
1285 	int rv;
1286 	uint_t *bp;
1287 	uint_t i, m;
1288 	u_quad_t q;
1289 
1290 	rv = 0;
1291 	bp = cp->c_bmp;
1292 	q = cp->c_off;
1293 	m = cp->c_mlen / BMAP_WSIZE;
1294 	for (i = 0; i < m; q += BMAP_BPW, bp++, i++)
1295 		if (*bp) {
1296 			rv = dbyte_apply_ifset(bmp, q, *bp, fp, arg);
1297 			if (rv != 0)
1298 				break;
1299 		}
1300 
1301 	return (rv);
1302 }
1303 
1304 
1305 /*
1306  * swfile_trunc
1307  *
1308  * Truncate the rest of the swap file.
1309  */
1310 static int
swfile_trunc(int fd)1311 swfile_trunc(int fd)
1312 {
1313 	int rv;
1314 	off_t off;
1315 
1316 	/*
1317 	 * Get the current offset and truncate whatever is
1318 	 * after this point.
1319 	 */
1320 	rv = 0;
1321 	if ((off = lseek(fd, 0, SEEK_CUR)) < 0)
1322 		rv = -1;
1323 	else if (ftruncate(fd, off) != 0)
1324 		rv = -1;
1325 
1326 	return (rv);
1327 }
1328 
1329 
1330 /*
1331  * swfile_init
1332  *
1333  * Initialize the swap file.  The necessary disk space is
1334  * reserved by writing to the swap file for swapping the
1335  * chunks in/out of the file.
1336  */
1337 static int
swfile_init(int fd,u_quad_t len,int set)1338 swfile_init(int fd, u_quad_t len, int set)
1339 {
1340 	u_quad_t i, n;
1341 	uint_t cl, ml;
1342 	uint_t buf[BMAP_CHUNK_WORDS];
1343 
1344 	(void) memset(buf, set ? 0xff : 0x00, BMAP_CHUNK_BYTES);
1345 	n = len / BMAP_CHUNK_BITS;
1346 	for (i = 0; i < n; i++)
1347 		if (write(fd, buf, BMAP_CHUNK_BYTES) != BMAP_CHUNK_BYTES)
1348 			return (-1);
1349 
1350 	cl = (uint_t)(len % BMAP_CHUNK_BITS);
1351 	ml = MEM_LEN(cl);
1352 	if (write(fd, buf, ml) != ml)
1353 		return (-1);
1354 
1355 	return (swfile_trunc(fd));
1356 }
1357 
1358 
1359 /*
1360  * dbm_alloc
1361  *
1362  * Allocate a bit map and return a handle to it.
1363  *
1364  * The swap file is created if it does not exist.
1365  * The file is truncated if it exists and is larger
1366  * than needed amount.
1367  *
1368  * The hash table and LRU list are empty at this point.
1369  * They are allocated and/or loaded on-demand.
1370  */
1371 int
dbm_alloc(char * fname,u_quad_t len,int set)1372 dbm_alloc(char *fname, u_quad_t len, int set)
1373 {
1374 	int fd;
1375 	int bmd;
1376 	dbitmap_t *bmp;
1377 
1378 	if (!fname || !*fname || !len)
1379 		return (-1);
1380 
1381 	/*
1382 	 * When allocating bitmap, make sure there is enough
1383 	 * disk space by allocating needed disk space, for
1384 	 * writing back the dirty chunks when swaping them out.
1385 	 */
1386 	bmd = dbmd_alloc();
1387 	if (bmd < 0)
1388 		return (bmd);
1389 
1390 	bmp = bmd2dbmp(bmd);
1391 	if ((fd = open(fname, O_RDWR|O_CREAT, 0600)) < 0)
1392 		bmd = -1;
1393 	else if (swfile_init(fd, len, set) < 0) {
1394 		bmd = -1;
1395 		(void) close(fd);
1396 		(void) unlink(fname);
1397 		dbmd_free(bmd);
1398 		bmd = -1;
1399 	} else if (!(bmp->bm_fname = strdup(fname))) {
1400 		(void) close(fd);
1401 		(void) unlink(fname);
1402 		dbmd_free(bmd);
1403 		bmd = -1;
1404 	} else {
1405 		bitmap_stats.bs_alloc_cnt++;
1406 		bitmap_stats.bs_alloc_size += len;
1407 
1408 		bmp->bm_fd = fd;
1409 		if (set)
1410 			BMAP_SET_FLAGS(bmp, BMAP_BINIT_ONES);
1411 		else
1412 			BMAP_UNSET_FLAGS(bmp, BMAP_BINIT_ONES);
1413 		bmp->bm_len = len;
1414 		bmp->bm_ccur = 0;
1415 		bmp->bm_cmax = BMAP_CHUNK_MAX;
1416 		TAILQ_INIT(&bmp->bm_lru);
1417 		hash_init((bmap_list_t *)bmp->bm_hash);
1418 	}
1419 
1420 	return (bmd);
1421 }
1422 
1423 
1424 /*
1425  * dbm_free
1426  *
1427  * Free memory allocated for the bitmap and remove its swap file.
1428  */
1429 int
dbm_free(int bmd)1430 dbm_free(int bmd)
1431 {
1432 	int rv;
1433 	dbitmap_t *bmp;
1434 
1435 	bmp = bmd2dbmp(bmd);
1436 	if (bmp && BMAP_IS_INUSE(bmp)) {
1437 		bitmap_stats.bs_free_cnt++;
1438 
1439 		dbm_chunks_free(bmp);
1440 		(void) close(bmp->bm_fd);
1441 		(void) unlink(bmp->bm_fname);
1442 		free(bmp->bm_fname);
1443 		dbmd_free(bmd);
1444 		rv = 0;
1445 	} else
1446 		rv = -1;
1447 
1448 	return (rv);
1449 }
1450 
1451 
1452 /*
1453  * dbm_getlen
1454  *
1455  * Return length of the bitmap.
1456  */
1457 u_quad_t
dbm_getlen(int bmd)1458 dbm_getlen(int bmd)
1459 {
1460 	dbitmap_t *bmp;
1461 
1462 	bmp = bmd2dbmp(bmd);
1463 	return (dbmp_getlen(bmp));
1464 }
1465 
1466 
1467 /*
1468  * dbm_set
1469  *
1470  * Set a range of bits.
1471  */
1472 int
dbm_set(int bmd,u_quad_t start,u_quad_t len,uint_t val)1473 dbm_set(int bmd, u_quad_t start, u_quad_t len, uint_t val)
1474 {
1475 	bm_io_t io;
1476 	bm_iovec_t iov;
1477 
1478 	iov.bmv_base = start;
1479 	iov.bmv_len = len;
1480 	iov.bmv_val = &val;
1481 	io.bmio_iovcnt = 1;
1482 	io.bmio_iov = &iov;
1483 
1484 	return (dbm_setiov(bmd, &io));
1485 }
1486 
1487 
1488 /*
1489  * dbm_getiov
1490  *
1491  * Get bits specified by the array of vectors.
1492  */
1493 int
dbm_getiov(int bmd,bm_io_t * iop)1494 dbm_getiov(int bmd, bm_io_t *iop)
1495 {
1496 	int i;
1497 	int rv;
1498 	bm_iovec_t *vp;
1499 	dbitmap_t *bmp;
1500 
1501 	if (!iop)
1502 		rv = -EINVAL;
1503 	else if (!(bmp = bmd2dbmp(bmd)))
1504 		rv = -EINVAL;
1505 	else if (iop->bmio_iovcnt <= 0)
1506 		rv = -EINVAL;
1507 	else {
1508 		rv = 0;
1509 		vp = iop->bmio_iov;
1510 		for (i = 0; i < iop->bmio_iovcnt; vp++, i++) {
1511 			if (!vp)
1512 				return (-EINVAL);
1513 			rv |= dbmp_getval(bmp, vp);
1514 		}
1515 	}
1516 
1517 	return (rv);
1518 }
1519 
1520 
1521 /*
1522  * dbm_setiov
1523  *
1524  * Set bits specified by the array of vectors.
1525  */
1526 int
dbm_setiov(int bmd,bm_io_t * iop)1527 dbm_setiov(int bmd, bm_io_t *iop)
1528 {
1529 	int i;
1530 	int rv;
1531 	bm_iovec_t *vp;
1532 	dbitmap_t *bmp;
1533 
1534 	if (!iop)
1535 		rv = -EINVAL;
1536 	else if (!(bmp = bmd2dbmp(bmd)))
1537 		rv = -EINVAL;
1538 	else if (iop->bmio_iovcnt <= 0)
1539 		rv = -EINVAL;
1540 	else if (!iop->bmio_iov)
1541 		rv = -EINVAL;
1542 	else {
1543 		rv = 0;
1544 		vp = iop->bmio_iov;
1545 		for (i = 0; i < iop->bmio_iovcnt; vp++, i++)
1546 			rv |= dbmp_setval(bmp, vp);
1547 	}
1548 
1549 	return (rv);
1550 }
1551 
1552 
1553 /*
1554  * dbm_apply_ifset
1555  *
1556  * Call the callback function for each set bit in the bitmap and
1557  * pass the 'arg' and bit number as its argument.
1558  */
1559 int
dbm_apply_ifset(int bmd,int (* fp)(),void * arg)1560 dbm_apply_ifset(int bmd, int(*fp)(), void *arg)
1561 {
1562 	int rv;
1563 	u_quad_t q;
1564 	dbitmap_t *bmp;
1565 	dbmap_chunk_t *cp;
1566 
1567 	bmp = bmd2dbmp(bmd);
1568 	if (!bmp || !fp)
1569 		return (-EINVAL);
1570 
1571 	rv = 0;
1572 	for (q = 0; q < bmp->bm_len; q += BMAP_CHUNK_BITS) {
1573 		cp = dbm_chunk_find(bmp, q);
1574 		if (!cp) {
1575 			rv = -ERANGE;
1576 			break;
1577 		}
1578 
1579 		rv = dbm_chunk_apply_ifset(bmp, cp, fp, arg);
1580 		if (rv != 0)
1581 			break;
1582 	}
1583 
1584 	return (rv);
1585 }
1586 
1587 
1588 /*
1589  * bm_set
1590  *
1591  * Set a range of bits.
1592  */
1593 int
bm_set(int bmd,u_quad_t start,u_quad_t len,uint_t val)1594 bm_set(int bmd, u_quad_t start, u_quad_t len, uint_t val)
1595 {
1596 	bm_io_t io;
1597 	bm_iovec_t iov;
1598 
1599 	iov.bmv_base = start;
1600 	iov.bmv_len = len;
1601 	iov.bmv_val = &val;
1602 	io.bmio_iovcnt = 1;
1603 	io.bmio_iov = &iov;
1604 
1605 	return (bm_setiov(bmd, &io));
1606 }
1607 
1608 
1609 /*
1610  * bm_get
1611  *
1612  * Get a range of bits.
1613  */
1614 int
bm_get(int bmd,u_quad_t start,u_quad_t len,uint_t * buf)1615 bm_get(int bmd, u_quad_t start, u_quad_t len, uint_t *buf)
1616 {
1617 	bm_io_t io;
1618 	bm_iovec_t iov;
1619 
1620 	iov.bmv_base = start;
1621 	iov.bmv_len = len;
1622 	iov.bmv_val = buf;
1623 	io.bmio_iovcnt = 1;
1624 	io.bmio_iov = &iov;
1625 
1626 	return (bm_getiov(bmd, &io));
1627 }
1628 
1629 
1630 /*
1631  * bm_getone
1632  *
1633  * Get only one bit.
1634  */
1635 int
bm_getone(int bmd,u_quad_t bitnum)1636 bm_getone(int bmd, u_quad_t bitnum)
1637 {
1638 	uint_t i;
1639 
1640 	if (bm_get(bmd, bitnum, 1, &i) == 0)
1641 		return (i ? 1 : 0);
1642 
1643 	return (0);
1644 }
1645 
1646 
1647 /*
1648  * dbm_get
1649  *
1650  * Get a range of bits.
1651  */
1652 int
dbm_get(int bmd,u_quad_t start,u_quad_t len,uint_t * buf)1653 dbm_get(int bmd, u_quad_t start, u_quad_t len, uint_t *buf)
1654 {
1655 	bm_io_t io;
1656 	bm_iovec_t iov;
1657 
1658 	iov.bmv_base = start;
1659 	iov.bmv_len = len;
1660 	iov.bmv_val = buf;
1661 	io.bmio_iovcnt = 1;
1662 	io.bmio_iov = &iov;
1663 
1664 	return (dbm_getiov(bmd, &io));
1665 }
1666 
1667 
1668 /*
1669  * dbm_getone
1670  *
1671  * Get only one bit.
1672  */
1673 int
dbm_getone(int bmd,u_quad_t bitnum)1674 dbm_getone(int bmd, u_quad_t bitnum)
1675 {
1676 	uint_t i;
1677 
1678 	if (dbm_get(bmd, bitnum, 1, &i) == 0)
1679 		return (i ? 1 : 0);
1680 
1681 	return (0);
1682 }
1683