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 (~(~0 << 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