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