xref: /illumos-gate/usr/src/cmd/ndmpd/tlm/tlm_bitmap.c (revision d21cedec)
12654012fSReza Sabdar /*
22654012fSReza Sabdar  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
32654012fSReza Sabdar  * Use is subject to license terms.
42654012fSReza Sabdar  */
52654012fSReza Sabdar 
62654012fSReza Sabdar /*
72654012fSReza Sabdar  * BSD 3 Clause License
82654012fSReza Sabdar  *
92654012fSReza Sabdar  * Copyright (c) 2007, The Storage Networking Industry Association.
102654012fSReza Sabdar  *
112654012fSReza Sabdar  * Redistribution and use in source and binary forms, with or without
122654012fSReza Sabdar  * modification, are permitted provided that the following conditions
132654012fSReza Sabdar  * are met:
142654012fSReza Sabdar  * 	- Redistributions of source code must retain the above copyright
152654012fSReza Sabdar  *	  notice, this list of conditions and the following disclaimer.
162654012fSReza Sabdar  *
172654012fSReza Sabdar  * 	- Redistributions in binary form must reproduce the above copyright
182654012fSReza Sabdar  *	  notice, this list of conditions and the following disclaimer in
192654012fSReza Sabdar  *	  the documentation and/or other materials provided with the
202654012fSReza Sabdar  *	  distribution.
212654012fSReza Sabdar  *
222654012fSReza Sabdar  *	- Neither the name of The Storage Networking Industry Association (SNIA)
232654012fSReza Sabdar  *	  nor the names of its contributors may be used to endorse or promote
242654012fSReza Sabdar  *	  products derived from this software without specific prior written
252654012fSReza Sabdar  *	  permission.
262654012fSReza Sabdar  *
272654012fSReza Sabdar  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
282654012fSReza Sabdar  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
292654012fSReza Sabdar  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
302654012fSReza Sabdar  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
312654012fSReza Sabdar  * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
322654012fSReza Sabdar  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
332654012fSReza Sabdar  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
342654012fSReza Sabdar  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
352654012fSReza Sabdar  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
362654012fSReza Sabdar  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
372654012fSReza Sabdar  * POSSIBILITY OF SUCH DAMAGE.
382654012fSReza Sabdar  */
392654012fSReza Sabdar #include <sys/types.h>
402654012fSReza Sabdar #include <sys/queue.h>
412654012fSReza Sabdar #include <bitmap.h>
422654012fSReza Sabdar #include <fcntl.h>
432654012fSReza Sabdar #include <stdio.h>
442654012fSReza Sabdar #include <stdlib.h>
452654012fSReza Sabdar #include <string.h>
462654012fSReza Sabdar #include <time.h>
472654012fSReza Sabdar #include <unistd.h>
482654012fSReza Sabdar #include <tlm.h>
492654012fSReza Sabdar 
502654012fSReza Sabdar 
512654012fSReza Sabdar /*
522654012fSReza Sabdar  * Hash table size.
532654012fSReza Sabdar  */
542654012fSReza Sabdar #define	BMAP_HASH_SIZE		64
552654012fSReza Sabdar 
562654012fSReza Sabdar 
572654012fSReza Sabdar /*
582654012fSReza Sabdar  * Maximum number of chunk that can be cached.
592654012fSReza Sabdar  */
602654012fSReza Sabdar #define	BMAP_CHUNK_MAX		128
612654012fSReza Sabdar 
622654012fSReza Sabdar 
632654012fSReza Sabdar /*
642654012fSReza Sabdar  * Size of bitmap table.
652654012fSReza Sabdar  */
662654012fSReza Sabdar #define	BMAP_MAX	256
672654012fSReza Sabdar 
682654012fSReza Sabdar 
692654012fSReza Sabdar /*
702654012fSReza Sabdar  * Bit_MAP Word SIZE.  This should be equal to 'sizeof (int)'.
712654012fSReza Sabdar  */
722654012fSReza Sabdar #define	BMAP_WSIZE	(sizeof (int))
732654012fSReza Sabdar 
742654012fSReza Sabdar 
752654012fSReza Sabdar /*
762654012fSReza Sabdar  * Bit_MAP Bit Per Word.
772654012fSReza Sabdar  */
782654012fSReza Sabdar #define	BMAP_BPW	(BMAP_WSIZE * 8)
792654012fSReza Sabdar #define	BMAP_BPW_SHIFT	5
80*d21cedecSToomas Soome #define	BMAP_BPW_MASK	(~(~0ULL << BMAP_BPW_SHIFT))
812654012fSReza Sabdar 
822654012fSReza Sabdar 
832654012fSReza Sabdar /*
842654012fSReza Sabdar  * Chunk of bit map in each node.
852654012fSReza Sabdar  */
862654012fSReza Sabdar #define	BMAP_CHUNK_WORDS	1024
872654012fSReza Sabdar #define	BMAP_CHUNK_BYTES	(BMAP_CHUNK_WORDS * BMAP_WSIZE)
882654012fSReza Sabdar #define	BMAP_CHUNK_BITS		(BMAP_CHUNK_WORDS * BMAP_BPW)
892654012fSReza Sabdar #define	BMAP_CHUNK_NO(p)	((p) / BMAP_CHUNK_BITS)
902654012fSReza Sabdar #define	BMAP_CHUNK_OFF(p)	(BMAP_CHUNK_NO(p) * BMAP_CHUNK_BITS)
912654012fSReza Sabdar 
922654012fSReza Sabdar 
932654012fSReza Sabdar /*
942654012fSReza Sabdar  * Bitmap flags.
952654012fSReza Sabdar  */
962654012fSReza Sabdar #define	BMAP_BINIT_ONES	0x00000001 /* initial value of bits is 1 */
972654012fSReza Sabdar #define	BMAP_INUSE	0x00000002 /* slot is in use */
982654012fSReza Sabdar 
992654012fSReza Sabdar 
1002654012fSReza Sabdar /*
1012654012fSReza Sabdar  * Macros of bitmap flags.
1022654012fSReza Sabdar  */
1032654012fSReza Sabdar #define	BMAP_SET_FLAGS(b, f)	((b)->bm_flags |= (f))
1042654012fSReza Sabdar #define	BMAP_UNSET_FLAGS(b, f)	((b)->bm_flags &= ~(f))
1052654012fSReza Sabdar 
1062654012fSReza Sabdar #define	BMAP_IS_INIT_ONES(b)	((b)->bm_flags & BMAP_BINIT_ONES)
1072654012fSReza Sabdar #define	BMAP_IS_INUSE(b)	((b)->bm_flags & BMAP_INUSE)
1082654012fSReza Sabdar 
1092654012fSReza Sabdar 
1102654012fSReza Sabdar #define	HASH(p)		(((p) / BMAP_CHUNK_BITS) % BMAP_HASH_SIZE)
1112654012fSReza Sabdar 
1122654012fSReza Sabdar /*
1132654012fSReza Sabdar  * Calculate the memory size in bytes needed for the specified length
1142654012fSReza Sabdar  * of bitmap.
1152654012fSReza Sabdar  */
1162654012fSReza Sabdar #define	ROUNDUP(n, d)	(((n) + (d) - 1) / (d))
1172654012fSReza Sabdar #define	MEM_LEN(l)	(ROUNDUP((l), BMAP_BPW) * BMAP_WSIZE)
1182654012fSReza Sabdar 
1192654012fSReza Sabdar 
1202654012fSReza Sabdar /*
1212654012fSReza Sabdar  * Chunk flags.
1222654012fSReza Sabdar  */
1232654012fSReza Sabdar #define	BMAP_CSET_DIRTY(cp)	(cp)->c_flags |= BMAP_CDIRTY
1242654012fSReza Sabdar #define	BMAP_CDIRTY	0x00000001 /* the chunk is dirty */
1252654012fSReza Sabdar 
1262654012fSReza Sabdar 
1272654012fSReza Sabdar /*
1282654012fSReza Sabdar  * Macros on chunk flags.
1292654012fSReza Sabdar  */
1302654012fSReza Sabdar #define	BMAP_CIS_DIRTY(cp)	((cp)->c_flags & BMAP_CDIRTY)
1312654012fSReza Sabdar 
1322654012fSReza Sabdar 
1332654012fSReza Sabdar /*
1342654012fSReza Sabdar  * When loading a bitmap chunk, if it is new set the bitmap
1352654012fSReza Sabdar  * can be set according to the initial value of bits.
1362654012fSReza Sabdar  * Otherwise, it should be loaded from the file.
1372654012fSReza Sabdar  */
1382654012fSReza Sabdar #define	BMAP_NEW_CHUNK		1
1392654012fSReza Sabdar #define	BMAP_OLD_CHUNK		0
1402654012fSReza Sabdar 
1412654012fSReza Sabdar /*
1422654012fSReza Sabdar  * Each chunk holds the followin information:
1432654012fSReza Sabdar  *  - A flag showing the status of the chunk, like being ditry or not.
1442654012fSReza Sabdar  *  - Its offset in bits from the beginning of the vector.
1452654012fSReza Sabdar  *  - Its length in bits.
1462654012fSReza Sabdar  *  - Its memory length in use in bytes.
1472654012fSReza Sabdar  *  - The bitmap vector.
1482654012fSReza Sabdar  *
1492654012fSReza Sabdar  *  In addition to the above information, each chunk can be on two lists:
1502654012fSReza Sabdar  *  one the hash list, the other LRU list.  The hash list is a MRU list,
1512654012fSReza Sabdar  *  meaning the MRU entry is at the head of the list.
1522654012fSReza Sabdar  *
1532654012fSReza Sabdar  *  All the chunks are in the LRU list. When a chunk is needed and there is
1542654012fSReza Sabdar  *  no more room for allocating chunks, the first entry of this list is
1552654012fSReza Sabdar  *  reclaimed.
1562654012fSReza Sabdar  */
1572654012fSReza Sabdar typedef struct dbmap_chunk {
1582654012fSReza Sabdar 	TAILQ_ENTRY(dbmap_chunk) c_hash;
1592654012fSReza Sabdar 	TAILQ_ENTRY(dbmap_chunk) c_lru;
1602654012fSReza Sabdar 	uint_t c_flags;
1612654012fSReza Sabdar 	u_quad_t c_off;
1622654012fSReza Sabdar 	uint_t c_clen;
1632654012fSReza Sabdar 	uint_t c_mlen;
1642654012fSReza Sabdar 	uint_t *c_bmp;
1652654012fSReza Sabdar } dbmap_chunk_t;
1662654012fSReza Sabdar 
1672654012fSReza Sabdar 
1682654012fSReza Sabdar TAILQ_HEAD(dbmap_list, dbmap_chunk);
1692654012fSReza Sabdar typedef struct dbmap_list dbmap_list_t;
1702654012fSReza Sabdar 
1712654012fSReza Sabdar 
1722654012fSReza Sabdar typedef struct dbitmap {
1732654012fSReza Sabdar 	char *bm_fname;
1742654012fSReza Sabdar 	int bm_fd;
1752654012fSReza Sabdar 	uint_t bm_flags;
1762654012fSReza Sabdar 	u_quad_t bm_len; /* bitmap length */
1772654012fSReza Sabdar 	uint_t bm_cmax; /* maximum number of cached chunks */
1782654012fSReza Sabdar 	uint_t bm_ccur; /* current number of cached chunks */
1792654012fSReza Sabdar 	dbmap_list_t bm_hash[BMAP_HASH_SIZE]; /* MRU hash table */
1802654012fSReza Sabdar 	dbmap_list_t bm_lru; /* LRU list */
1812654012fSReza Sabdar } dbitmap_t;
1822654012fSReza Sabdar 
1832654012fSReza Sabdar /*
1842654012fSReza Sabdar  * Disk bitmap table.  Upon allocating a dbitmap, one slot
1852654012fSReza Sabdar  * of this table will be used.
1862654012fSReza Sabdar  */
1872654012fSReza Sabdar static dbitmap_t dbitmap[BMAP_MAX];
1882654012fSReza Sabdar 
1892654012fSReza Sabdar 
1902654012fSReza Sabdar /*
1912654012fSReza Sabdar  * Each chunk holds the followin information:
1922654012fSReza Sabdar  *  - Its offset in bits from the beginning of the vector.
1932654012fSReza Sabdar  *  - Its length in bits.
1942654012fSReza Sabdar  *  - Its memory length in use in bytes.
1952654012fSReza Sabdar  *  - The bitmap vector.
1962654012fSReza Sabdar  *
1972654012fSReza Sabdar  *  In addition to the above information, each chunk can be on a list:
1982654012fSReza Sabdar  *  one the hash list.  The hash list is a MRU list,  meaning that the
1992654012fSReza Sabdar  *  MRU entry is at the head of the list.
2002654012fSReza Sabdar  */
2012654012fSReza Sabdar typedef struct bmap_chunk {
2022654012fSReza Sabdar 	TAILQ_ENTRY(bmap_chunk) c_hash;
2032654012fSReza Sabdar 	u_quad_t c_off;
2042654012fSReza Sabdar 	uint_t c_clen;
2052654012fSReza Sabdar 	uint_t c_mlen;
2062654012fSReza Sabdar 	uint_t *c_bmp;
2072654012fSReza Sabdar } bmap_chunk_t;
2082654012fSReza Sabdar 
2092654012fSReza Sabdar 
2102654012fSReza Sabdar TAILQ_HEAD(bmap_list, bmap_chunk);
2112654012fSReza Sabdar typedef struct bmap_list bmap_list_t;
2122654012fSReza Sabdar 
2132654012fSReza Sabdar 
2142654012fSReza Sabdar typedef struct bitmap {
2152654012fSReza Sabdar 	uint_t bm_flags;
2162654012fSReza Sabdar 	u_quad_t bm_len; /* bitmap length */
2172654012fSReza Sabdar 	uint_t bm_cmax; /* maximum number of cached chunks */
2182654012fSReza Sabdar 	uint_t bm_ccur; /* current number of cached chunks */
2192654012fSReza Sabdar 	bmap_list_t bm_hash[BMAP_HASH_SIZE]; /* MRU hash table */
2202654012fSReza Sabdar } bitmap_t;
2212654012fSReza Sabdar 
2222654012fSReza Sabdar 
2232654012fSReza Sabdar /*
2242654012fSReza Sabdar  * Statistics gathering structure.
2252654012fSReza Sabdar  */
2262654012fSReza Sabdar typedef struct bitmap_stats {
2272654012fSReza Sabdar 	ulong_t bs_alloc_cnt;
2282654012fSReza Sabdar 	ulong_t bs_alloc_size;
2292654012fSReza Sabdar 	ulong_t bs_free_cnt;
2302654012fSReza Sabdar 	ulong_t bs_set_applied;
2312654012fSReza Sabdar 	ulong_t bs_unset_applied;
2322654012fSReza Sabdar 	ulong_t bs_cache_hit;
2332654012fSReza Sabdar 	ulong_t bs_cache_miss;
2342654012fSReza Sabdar 	ulong_t bs_chunk_new;
2352654012fSReza Sabdar 	ulong_t bs_chunk_flush;
2362654012fSReza Sabdar 	ulong_t bs_chunk_reclaim;
2372654012fSReza Sabdar 	u_quad_t bs_get;
2382654012fSReza Sabdar 	u_quad_t bs_get_bits;
2392654012fSReza Sabdar 	u_quad_t bs_set;
2402654012fSReza Sabdar 	u_quad_t bs_set_bits;
2412654012fSReza Sabdar 	u_quad_t bs_unset;
2422654012fSReza Sabdar 	u_quad_t bs_unset_bits;
2432654012fSReza Sabdar } bitmap_stats_t;
2442654012fSReza Sabdar 
2452654012fSReza Sabdar 
2462654012fSReza Sabdar /*
2472654012fSReza Sabdar  * Disk bitmap table.  Upon allocating a bitmap, one slot
2482654012fSReza Sabdar  * of this table will be used.
2492654012fSReza Sabdar  */
2502654012fSReza Sabdar static bitmap_t bitmap[BMAP_MAX];
2512654012fSReza Sabdar 
2522654012fSReza Sabdar 
2532654012fSReza Sabdar /*
2542654012fSReza Sabdar  * Global instance of statistics variable.
2552654012fSReza Sabdar  */
2562654012fSReza Sabdar bitmap_stats_t bitmap_stats;
2572654012fSReza Sabdar 
2582654012fSReza Sabdar 
2592654012fSReza Sabdar /*
2602654012fSReza Sabdar  * bmd2bmp
2612654012fSReza Sabdar  *
2622654012fSReza Sabdar  * Convert bitmap descriptor to bitmap pointer.
2632654012fSReza Sabdar  */
2642654012fSReza Sabdar static bitmap_t *
bmd2bmp(int bmd)2652654012fSReza Sabdar bmd2bmp(int bmd)
2662654012fSReza Sabdar {
2672654012fSReza Sabdar 	if (bmd < 0 || bmd >= BMAP_MAX)
2682654012fSReza Sabdar 		return (NULL);
2692654012fSReza Sabdar 
2702654012fSReza Sabdar 	return (&bitmap[bmd]);
2712654012fSReza Sabdar }
2722654012fSReza Sabdar 
2732654012fSReza Sabdar 
2742654012fSReza Sabdar /*
2752654012fSReza Sabdar  * bmd_alloc
2762654012fSReza Sabdar  *
2772654012fSReza Sabdar  * Allocate a bitmap descriptor.  Sets the INUSE flag of the slot.
2782654012fSReza Sabdar  */
2792654012fSReza Sabdar static int
bmd_alloc(void)2802654012fSReza Sabdar bmd_alloc(void)
2812654012fSReza Sabdar {
2822654012fSReza Sabdar 	int i;
2832654012fSReza Sabdar 	bitmap_t *bmp;
2842654012fSReza Sabdar 
2852654012fSReza Sabdar 	bmp = bitmap;
2862654012fSReza Sabdar 	for (i = 0; i < BMAP_MAX; bmp++, i++)
2872654012fSReza Sabdar 		if (!BMAP_IS_INUSE(bmp)) {
2882654012fSReza Sabdar 			BMAP_SET_FLAGS(bmp, BMAP_INUSE);
2892654012fSReza Sabdar 			return (i);
2902654012fSReza Sabdar 		}
2912654012fSReza Sabdar 
2922654012fSReza Sabdar 	return (-1);
2932654012fSReza Sabdar }
2942654012fSReza Sabdar 
2952654012fSReza Sabdar 
2962654012fSReza Sabdar /*
2972654012fSReza Sabdar  * bmd_free
2982654012fSReza Sabdar  *
2992654012fSReza Sabdar  * Free a bitmap descriptor.  Clears the INUSE flag of the slot.
3002654012fSReza Sabdar  */
3012654012fSReza Sabdar static void
bmd_free(int bmd)3022654012fSReza Sabdar bmd_free(int bmd)
3032654012fSReza Sabdar {
3042654012fSReza Sabdar 	bitmap_t *bmp;
3052654012fSReza Sabdar 
3062654012fSReza Sabdar 	bmp = bmd2bmp(bmd);
3072654012fSReza Sabdar 	if (bmp)
3082654012fSReza Sabdar 		BMAP_UNSET_FLAGS(bmp, BMAP_INUSE);
3092654012fSReza Sabdar }
3102654012fSReza Sabdar 
3112654012fSReza Sabdar 
3122654012fSReza Sabdar /*
3132654012fSReza Sabdar  * bmp_set
3142654012fSReza Sabdar  *
3152654012fSReza Sabdar  * Generic function to set bit in a chunk.  This can set or unset the
3162654012fSReza Sabdar  * specified bit.
3172654012fSReza Sabdar  */
3182654012fSReza Sabdar static inline int
bmp_set(bmap_chunk_t * cp,u_quad_t bn,uint_t * vp)3192654012fSReza Sabdar bmp_set(bmap_chunk_t *cp, u_quad_t bn, uint_t *vp)
3202654012fSReza Sabdar {
3212654012fSReza Sabdar 	int rv;
3222654012fSReza Sabdar 	uint_t mask;
3232654012fSReza Sabdar 	uint_t *ip;
3242654012fSReza Sabdar 	uint_t v;
3252654012fSReza Sabdar 
3262654012fSReza Sabdar 	bn -= cp->c_off;
3272654012fSReza Sabdar 	if (bn < cp->c_clen) {
3282654012fSReza Sabdar 		mask = 1 <<(bn & BMAP_BPW_MASK);
3292654012fSReza Sabdar 		ip = &cp->c_bmp[bn >> BMAP_BPW_SHIFT];
3302654012fSReza Sabdar 		v = (*vp <<(bn & BMAP_BPW_MASK)) & mask;
3312654012fSReza Sabdar 		*ip = (*ip & ~mask) | v;
3322654012fSReza Sabdar 		rv = 0;
3332654012fSReza Sabdar 	} else
3342654012fSReza Sabdar 		rv = -ERANGE;
3352654012fSReza Sabdar 
3362654012fSReza Sabdar 	return (rv);
3372654012fSReza Sabdar }
3382654012fSReza Sabdar 
3392654012fSReza Sabdar 
3402654012fSReza Sabdar /*
3412654012fSReza Sabdar  * bmp_get
3422654012fSReza Sabdar  *
3432654012fSReza Sabdar  * Generic function to get bit in a chunk.
3442654012fSReza Sabdar  */
3452654012fSReza Sabdar static inline int
bmp_get(bmap_chunk_t * cp,u_quad_t bn)3462654012fSReza Sabdar bmp_get(bmap_chunk_t *cp, u_quad_t bn)
3472654012fSReza Sabdar {
3482654012fSReza Sabdar 	int rv;
3492654012fSReza Sabdar 	uint_t bit;
3502654012fSReza Sabdar 
3512654012fSReza Sabdar 	bn -= cp->c_off;
3522654012fSReza Sabdar 	if (bn < cp->c_clen) {
3532654012fSReza Sabdar 		bit = 1 <<(bn & BMAP_BPW_MASK);
3542654012fSReza Sabdar 		rv = (cp->c_bmp[bn >> BMAP_BPW_SHIFT] & bit) != 0;
3552654012fSReza Sabdar 	} else
3562654012fSReza Sabdar 		rv = -ERANGE;
3572654012fSReza Sabdar 
3582654012fSReza Sabdar 	return (rv);
3592654012fSReza Sabdar }
3602654012fSReza Sabdar 
3612654012fSReza Sabdar 
3622654012fSReza Sabdar /*
3632654012fSReza Sabdar  * bm_chuck_setup
3642654012fSReza Sabdar  *
3652654012fSReza Sabdar  * Set up the properties of the new chunk and position it in the hash list.
3662654012fSReza Sabdar  */
3672654012fSReza Sabdar static bmap_chunk_t *
bm_chunk_setup(bitmap_t * bmp,bmap_chunk_t * cp,u_quad_t bn)3682654012fSReza Sabdar bm_chunk_setup(bitmap_t *bmp, bmap_chunk_t *cp, u_quad_t bn)
3692654012fSReza Sabdar {
3702654012fSReza Sabdar 	int h;
3712654012fSReza Sabdar 	u_quad_t off, l;
3722654012fSReza Sabdar 	uint_t cl, ml;
3732654012fSReza Sabdar 	bmap_list_t *hp;
3742654012fSReza Sabdar 
3752654012fSReza Sabdar 	off = BMAP_CHUNK_OFF(bn);
3762654012fSReza Sabdar 	l = bmp->bm_len - off;
3772654012fSReza Sabdar 	if (l >= BMAP_CHUNK_BITS) {
3782654012fSReza Sabdar 		cl = BMAP_CHUNK_BITS;
3792654012fSReza Sabdar 		ml = BMAP_CHUNK_BYTES;
3802654012fSReza Sabdar 	} else {
3812654012fSReza Sabdar 		cl = l;
3822654012fSReza Sabdar 		ml = MEM_LEN(l);
3832654012fSReza Sabdar 	}
3842654012fSReza Sabdar 
3852654012fSReza Sabdar 	if (BMAP_IS_INIT_ONES(bmp))
3862654012fSReza Sabdar 		(void) memset(cp->c_bmp, 0xff, ml);
3872654012fSReza Sabdar 	else
3882654012fSReza Sabdar 		(void) memset(cp->c_bmp, 0x00, ml);
3892654012fSReza Sabdar 
3902654012fSReza Sabdar 	h = HASH(bn);
3912654012fSReza Sabdar 	hp = &bmp->bm_hash[h];
3922654012fSReza Sabdar 
3932654012fSReza Sabdar 	TAILQ_INSERT_HEAD(hp, cp, c_hash);
3942654012fSReza Sabdar 	cp->c_off = off;
3952654012fSReza Sabdar 	cp->c_clen = cl;
3962654012fSReza Sabdar 	cp->c_mlen = ml;
3972654012fSReza Sabdar 	return (cp);
3982654012fSReza Sabdar }
3992654012fSReza Sabdar 
4002654012fSReza Sabdar 
4012654012fSReza Sabdar /*
4022654012fSReza Sabdar  * bm_chunk_new
4032654012fSReza Sabdar  *
4042654012fSReza Sabdar  * Create a new chunk and keep track of memory used.
4052654012fSReza Sabdar  */
4062654012fSReza Sabdar static bmap_chunk_t *
bm_chunk_new(bitmap_t * bmp,u_quad_t bn)4072654012fSReza Sabdar bm_chunk_new(bitmap_t *bmp, u_quad_t bn)
4082654012fSReza Sabdar {
4092654012fSReza Sabdar 	bmap_chunk_t *cp;
4102654012fSReza Sabdar 
4112654012fSReza Sabdar 	bitmap_stats.bs_chunk_new++;
4122654012fSReza Sabdar 
4132654012fSReza Sabdar 	cp = ndmp_malloc(sizeof (bmap_chunk_t));
4142654012fSReza Sabdar 	if (cp) {
4152654012fSReza Sabdar 		cp->c_bmp = ndmp_malloc(sizeof (uint_t) * BMAP_CHUNK_WORDS);
4162654012fSReza Sabdar 		if (!cp->c_bmp) {
4172654012fSReza Sabdar 			free(cp);
4182654012fSReza Sabdar 			cp = NULL;
4192654012fSReza Sabdar 		} else {
4202654012fSReza Sabdar 			(void) bm_chunk_setup(bmp, cp, bn);
4212654012fSReza Sabdar 			bmp->bm_ccur++;
4222654012fSReza Sabdar 		}
4232654012fSReza Sabdar 	}
4242654012fSReza Sabdar 
4252654012fSReza Sabdar 	return (cp);
4262654012fSReza Sabdar }
4272654012fSReza Sabdar 
4282654012fSReza Sabdar 
4292654012fSReza Sabdar /*
4302654012fSReza Sabdar  * bm_chunk_alloc
4312654012fSReza Sabdar  *
4322654012fSReza Sabdar  * Allocate a chunk and return it.  If the cache for the chunks is not
4332654012fSReza Sabdar  * fully used, a new chunk is created.
4342654012fSReza Sabdar  */
4352654012fSReza Sabdar static bmap_chunk_t *
bm_chunk_alloc(bitmap_t * bmp,u_quad_t bn)4362654012fSReza Sabdar bm_chunk_alloc(bitmap_t *bmp, u_quad_t bn)
4372654012fSReza Sabdar {
4382654012fSReza Sabdar 	bmap_chunk_t *cp;
4392654012fSReza Sabdar 
4402654012fSReza Sabdar 	if (bmp->bm_ccur < bmp->bm_cmax)
4412654012fSReza Sabdar 		cp = bm_chunk_new(bmp, bn);
4422654012fSReza Sabdar 	else
4432654012fSReza Sabdar 		cp = NULL;
4442654012fSReza Sabdar 
4452654012fSReza Sabdar 	return (cp);
4462654012fSReza Sabdar }
4472654012fSReza Sabdar 
4482654012fSReza Sabdar 
4492654012fSReza Sabdar /*
4502654012fSReza Sabdar  * hash_free
4512654012fSReza Sabdar  *
4522654012fSReza Sabdar  * Free all chunks on the hash list.
4532654012fSReza Sabdar  */
4542654012fSReza Sabdar void
hash_free(bmap_list_t * hp)4552654012fSReza Sabdar hash_free(bmap_list_t *hp)
4562654012fSReza Sabdar {
4572654012fSReza Sabdar 	bmap_chunk_t *cp;
4582654012fSReza Sabdar 
4592654012fSReza Sabdar 	if (!hp)
4602654012fSReza Sabdar 		return;
4612654012fSReza Sabdar 
4622654012fSReza Sabdar 	while (!TAILQ_EMPTY(hp)) {
4632654012fSReza Sabdar 		cp = TAILQ_FIRST(hp);
4642654012fSReza Sabdar 		TAILQ_REMOVE(hp, cp, c_hash);
4652654012fSReza Sabdar 		free(cp->c_bmp);
4662654012fSReza Sabdar 		free(cp);
4672654012fSReza Sabdar 	}
4682654012fSReza Sabdar }
4692654012fSReza Sabdar 
4702654012fSReza Sabdar 
4712654012fSReza Sabdar /*
4722654012fSReza Sabdar  * bm_chunks_free
4732654012fSReza Sabdar  *
4742654012fSReza Sabdar  * Release the memory allocated for the chunks.
4752654012fSReza Sabdar  */
4762654012fSReza Sabdar static void
bm_chunks_free(bmap_list_t * hp)4772654012fSReza Sabdar bm_chunks_free(bmap_list_t *hp)
4782654012fSReza Sabdar {
4792654012fSReza Sabdar 	int i;
4802654012fSReza Sabdar 
4812654012fSReza Sabdar 	for (i = 0; i < BMAP_HASH_SIZE; hp++, i++)
4822654012fSReza Sabdar 		hash_free(hp);
4832654012fSReza Sabdar }
4842654012fSReza Sabdar 
4852654012fSReza Sabdar 
4862654012fSReza Sabdar /*
4872654012fSReza Sabdar  * bm_chunk_repositions
4882654012fSReza Sabdar  *
4892654012fSReza Sabdar  * Re-position the chunk in the MRU hash table.
4902654012fSReza Sabdar  */
4912654012fSReza Sabdar static void
bm_chunk_reposition(bitmap_t * bmp,bmap_list_t * hp,bmap_chunk_t * cp)4922654012fSReza Sabdar bm_chunk_reposition(bitmap_t *bmp, bmap_list_t *hp, bmap_chunk_t *cp)
4932654012fSReza Sabdar {
4942654012fSReza Sabdar 	if (!bmp || !hp || !cp)
4952654012fSReza Sabdar 		return;
4962654012fSReza Sabdar 
4972654012fSReza Sabdar 	if (TAILQ_FIRST(hp) != cp) {
4982654012fSReza Sabdar 		TAILQ_REMOVE(hp, cp, c_hash);
4992654012fSReza Sabdar 		TAILQ_INSERT_HEAD(hp, cp, c_hash);
5002654012fSReza Sabdar 	}
5012654012fSReza Sabdar }
5022654012fSReza Sabdar 
5032654012fSReza Sabdar 
5042654012fSReza Sabdar /*
5052654012fSReza Sabdar  * bm_chunk_find
5062654012fSReza Sabdar  *
5072654012fSReza Sabdar  * Find and return the chunks which holds the specified bit. Allocate
5082654012fSReza Sabdar  * the chunk if necessary and re-position it in the hash table lists.
5092654012fSReza Sabdar  */
5102654012fSReza Sabdar static bmap_chunk_t *
bm_chunk_find(bitmap_t * bmp,u_quad_t bn)5112654012fSReza Sabdar bm_chunk_find(bitmap_t *bmp, u_quad_t bn)
5122654012fSReza Sabdar {
5132654012fSReza Sabdar 	int h;
5142654012fSReza Sabdar 	bmap_chunk_t *cp;
5152654012fSReza Sabdar 	bmap_list_t *hp;
5162654012fSReza Sabdar 
5172654012fSReza Sabdar 	if (!bmp)
5182654012fSReza Sabdar 		return (NULL);
5192654012fSReza Sabdar 
5202654012fSReza Sabdar 	h = HASH(bn);
5212654012fSReza Sabdar 	hp = &bmp->bm_hash[h];
5222654012fSReza Sabdar 	TAILQ_FOREACH(cp, hp, c_hash) {
5232654012fSReza Sabdar 		if (bn >= cp->c_off && bn < (cp->c_off + cp->c_clen)) {
5242654012fSReza Sabdar 			bitmap_stats.bs_cache_hit++;
5252654012fSReza Sabdar 
5262654012fSReza Sabdar 			bm_chunk_reposition(bmp, hp, cp);
5272654012fSReza Sabdar 			return (cp);
5282654012fSReza Sabdar 		}
5292654012fSReza Sabdar 	}
5302654012fSReza Sabdar 
5312654012fSReza Sabdar 	bitmap_stats.bs_cache_miss++;
5322654012fSReza Sabdar 
5332654012fSReza Sabdar 	return (bm_chunk_alloc(bmp, bn));
5342654012fSReza Sabdar }
5352654012fSReza Sabdar 
5362654012fSReza Sabdar 
5372654012fSReza Sabdar /*
5382654012fSReza Sabdar  * bmp_setval
5392654012fSReza Sabdar  *
5402654012fSReza Sabdar  * Set a range of bits in the bitmap specified by the vector.
5412654012fSReza Sabdar  */
5422654012fSReza Sabdar static int
bmp_setval(bitmap_t * bmp,bm_iovec_t * vp)5432654012fSReza Sabdar bmp_setval(bitmap_t *bmp, bm_iovec_t *vp)
5442654012fSReza Sabdar {
5452654012fSReza Sabdar 	int rv;
5462654012fSReza Sabdar 	u_quad_t cl;
5472654012fSReza Sabdar 	u_quad_t bn;
5482654012fSReza Sabdar 	u_quad_t max;
5492654012fSReza Sabdar 	bmap_chunk_t *cp;
5502654012fSReza Sabdar 
5512654012fSReza Sabdar 	bn = vp->bmv_base;
5522654012fSReza Sabdar 	max = bn + vp->bmv_len;
5532654012fSReza Sabdar 	if (bn >= bmp->bm_len || max > bmp->bm_len)
5542654012fSReza Sabdar 		return (-EINVAL);
5552654012fSReza Sabdar 
5562654012fSReza Sabdar 	if (*vp->bmv_val) {
5572654012fSReza Sabdar 		bitmap_stats.bs_set++;
5582654012fSReza Sabdar 		bitmap_stats.bs_set_bits += vp->bmv_len;
5592654012fSReza Sabdar 	} else {
5602654012fSReza Sabdar 		bitmap_stats.bs_unset++;
5612654012fSReza Sabdar 		bitmap_stats.bs_unset_bits += vp->bmv_len;
5622654012fSReza Sabdar 	}
5632654012fSReza Sabdar 
5642654012fSReza Sabdar 	do {
5652654012fSReza Sabdar 		cp = bm_chunk_find(bmp, bn);
5662654012fSReza Sabdar 		if (!cp)
5672654012fSReza Sabdar 			return (-ERANGE);
5682654012fSReza Sabdar 
5692654012fSReza Sabdar 		for (cl = cp->c_off + cp->c_clen; bn < cl && bn < max; bn++) {
5702654012fSReza Sabdar 			rv = bmp_set(cp, bn, vp->bmv_val);
5712654012fSReza Sabdar 			if (rv != 0)
5722654012fSReza Sabdar 				return (rv);
5732654012fSReza Sabdar 		}
5742654012fSReza Sabdar 	} while (bn < max);
5752654012fSReza Sabdar 
5762654012fSReza Sabdar 	return (0);
5772654012fSReza Sabdar }
5782654012fSReza Sabdar 
5792654012fSReza Sabdar 
5802654012fSReza Sabdar /*
5812654012fSReza Sabdar  * bmp_getval
5822654012fSReza Sabdar  *
5832654012fSReza Sabdar  * Get a range of bits in the bitmap specified by the vector.
5842654012fSReza Sabdar  */
5852654012fSReza Sabdar static int
bmp_getval(bitmap_t * bmp,bm_iovec_t * vp)5862654012fSReza Sabdar bmp_getval(bitmap_t *bmp, bm_iovec_t *vp)
5872654012fSReza Sabdar {
5882654012fSReza Sabdar 	uint_t cnt;
5892654012fSReza Sabdar 	uint_t *ip;
5902654012fSReza Sabdar 	int rv;
5912654012fSReza Sabdar 	u_quad_t cl;
5922654012fSReza Sabdar 	u_quad_t bn;
5932654012fSReza Sabdar 	u_quad_t max;
5942654012fSReza Sabdar 	bmap_chunk_t *cp;
5952654012fSReza Sabdar 
5962654012fSReza Sabdar 	bn = vp->bmv_base;
5972654012fSReza Sabdar 	max = bn + vp->bmv_len;
5982654012fSReza Sabdar 	if (bn >= bmp->bm_len || max > bmp->bm_len)
5992654012fSReza Sabdar 		return (-EINVAL);
6002654012fSReza Sabdar 
6012654012fSReza Sabdar 	bitmap_stats.bs_get++;
6022654012fSReza Sabdar 	bitmap_stats.bs_get_bits += 1;
6032654012fSReza Sabdar 
6042654012fSReza Sabdar 	cnt = 0;
6052654012fSReza Sabdar 	ip = vp->bmv_val;
6062654012fSReza Sabdar 	*ip = 0;
6072654012fSReza Sabdar 	do {
6082654012fSReza Sabdar 		cp = bm_chunk_find(bmp, bn);
6092654012fSReza Sabdar 		if (!cp)
6102654012fSReza Sabdar 			return (-ERANGE);
6112654012fSReza Sabdar 
6122654012fSReza Sabdar 		for (cl = cp->c_off + cp->c_clen; bn < cl && bn < max; bn++) {
6132654012fSReza Sabdar 			rv = bmp_get(cp, bn);
6142654012fSReza Sabdar 			if (rv < 0)
6152654012fSReza Sabdar 				return (rv);
6162654012fSReza Sabdar 
6172654012fSReza Sabdar 			*ip |= rv << cnt;
6182654012fSReza Sabdar 			if (++cnt >= BMAP_BPW) {
6192654012fSReza Sabdar 				*++ip = 0;
6202654012fSReza Sabdar 				cnt = 0;
6212654012fSReza Sabdar 			}
6222654012fSReza Sabdar 		}
6232654012fSReza Sabdar 	} while (bn < max);
6242654012fSReza Sabdar 
6252654012fSReza Sabdar 	return (0);
6262654012fSReza Sabdar }
6272654012fSReza Sabdar 
6282654012fSReza Sabdar 
6292654012fSReza Sabdar /*
6302654012fSReza Sabdar  * hash_init
6312654012fSReza Sabdar  *
6322654012fSReza Sabdar  * Initialize the hash table lists head.
6332654012fSReza Sabdar  */
6342654012fSReza Sabdar static void
hash_init(bmap_list_t * hp)6352654012fSReza Sabdar hash_init(bmap_list_t *hp)
6362654012fSReza Sabdar {
6372654012fSReza Sabdar 	int i;
6382654012fSReza Sabdar 
6392654012fSReza Sabdar 	for (i = 0; i < BMAP_HASH_SIZE; hp++, i++) {
6402654012fSReza Sabdar 		TAILQ_INIT(hp);
6412654012fSReza Sabdar 	}
6422654012fSReza Sabdar }
6432654012fSReza Sabdar 
6442654012fSReza Sabdar 
6452654012fSReza Sabdar /*
6462654012fSReza Sabdar  * bm_alloc
6472654012fSReza Sabdar  *
6482654012fSReza Sabdar  * Allocate a bit map and return a handle to it.
6492654012fSReza Sabdar  *
6502654012fSReza Sabdar  * The hash table list are empty at this point. They are allocated
6512654012fSReza Sabdar  * on demand.
6522654012fSReza Sabdar  */
6532654012fSReza Sabdar int
bm_alloc(u_quad_t len,int set)6542654012fSReza Sabdar bm_alloc(u_quad_t len, int set)
6552654012fSReza Sabdar {
6562654012fSReza Sabdar 	int bmd;
6572654012fSReza Sabdar 	bitmap_t *bmp;
6582654012fSReza Sabdar 
6592654012fSReza Sabdar 	if (len == 0)
6602654012fSReza Sabdar 		return (-1);
6612654012fSReza Sabdar 
6622654012fSReza Sabdar 	bmd = bmd_alloc();
6632654012fSReza Sabdar 	if (bmd < 0)
6642654012fSReza Sabdar 		return (bmd);
6652654012fSReza Sabdar 
6662654012fSReza Sabdar 	bmp = bmd2bmp(bmd);
6672654012fSReza Sabdar 	bitmap_stats.bs_alloc_cnt++;
6682654012fSReza Sabdar 	bitmap_stats.bs_alloc_size += len;
6692654012fSReza Sabdar 
6702654012fSReza Sabdar 	if (set)
6712654012fSReza Sabdar 		BMAP_SET_FLAGS(bmp, BMAP_BINIT_ONES);
6722654012fSReza Sabdar 	else
6732654012fSReza Sabdar 		BMAP_UNSET_FLAGS(bmp, BMAP_BINIT_ONES);
6742654012fSReza Sabdar 	bmp->bm_len = len;
6752654012fSReza Sabdar 	bmp->bm_ccur = 0;
6762654012fSReza Sabdar 	bmp->bm_cmax = BMAP_CHUNK_MAX;
6772654012fSReza Sabdar 	hash_init(bmp->bm_hash);
6782654012fSReza Sabdar 
6792654012fSReza Sabdar 	return (bmd);
6802654012fSReza Sabdar }
6812654012fSReza Sabdar 
6822654012fSReza Sabdar 
6832654012fSReza Sabdar /*
6842654012fSReza Sabdar  * bm_free
6852654012fSReza Sabdar  *
6862654012fSReza Sabdar  * Free memory allocated for the bitmap.
6872654012fSReza Sabdar  */
6882654012fSReza Sabdar int
bm_free(int bmd)6892654012fSReza Sabdar bm_free(int bmd)
6902654012fSReza Sabdar {
6912654012fSReza Sabdar 	int rv;
6922654012fSReza Sabdar 	bitmap_t *bmp;
6932654012fSReza Sabdar 
6942654012fSReza Sabdar 	bmp = bmd2bmp(bmd);
6952654012fSReza Sabdar 	if (bmp && BMAP_IS_INUSE(bmp)) {
6962654012fSReza Sabdar 		bitmap_stats.bs_free_cnt++;
6972654012fSReza Sabdar 
6982654012fSReza Sabdar 		bm_chunks_free(bmp->bm_hash);
6992654012fSReza Sabdar 		bmd_free(bmd);
7002654012fSReza Sabdar 		rv = 0;
7012654012fSReza Sabdar 	} else
7022654012fSReza Sabdar 		rv = -1;
7032654012fSReza Sabdar 
7042654012fSReza Sabdar 	return (rv);
7052654012fSReza Sabdar }
7062654012fSReza Sabdar 
7072654012fSReza Sabdar 
7082654012fSReza Sabdar /*
7092654012fSReza Sabdar  * bm_getiov
7102654012fSReza Sabdar  *
7112654012fSReza Sabdar  * Get bits specified by the array of vectors.
7122654012fSReza Sabdar  */
7132654012fSReza Sabdar int
bm_getiov(int bmd,bm_io_t * iop)7142654012fSReza Sabdar bm_getiov(int bmd, bm_io_t *iop)
7152654012fSReza Sabdar {
7162654012fSReza Sabdar 	int i;
7172654012fSReza Sabdar 	int rv;
7182654012fSReza Sabdar 	bm_iovec_t *vp;
7192654012fSReza Sabdar 	bitmap_t *bmp;
7202654012fSReza Sabdar 
7212654012fSReza Sabdar 	if (!iop)
7222654012fSReza Sabdar 		rv = -EINVAL;
7232654012fSReza Sabdar 	else if (!(bmp = bmd2bmp(bmd)))
7242654012fSReza Sabdar 		rv = -EINVAL;
7252654012fSReza Sabdar 	else if (iop->bmio_iovcnt <= 0)
7262654012fSReza Sabdar 		rv = -EINVAL;
7272654012fSReza Sabdar 	else {
7282654012fSReza Sabdar 		rv = 0;
7292654012fSReza Sabdar 		vp = iop->bmio_iov;
7302654012fSReza Sabdar 		for (i = 0; i < iop->bmio_iovcnt; vp++, i++) {
7312654012fSReza Sabdar 			if (!vp)
7322654012fSReza Sabdar 				return (-EINVAL);
7332654012fSReza Sabdar 			rv |= bmp_getval(bmp, vp);
7342654012fSReza Sabdar 		}
7352654012fSReza Sabdar 	}
7362654012fSReza Sabdar 
7372654012fSReza Sabdar 	return (rv);
7382654012fSReza Sabdar }
7392654012fSReza Sabdar 
7402654012fSReza Sabdar 
7412654012fSReza Sabdar /*
7422654012fSReza Sabdar  * bm_setiov
7432654012fSReza Sabdar  *
7442654012fSReza Sabdar  * Set bits specified by the array of vectors.
7452654012fSReza Sabdar  */
7462654012fSReza Sabdar int
bm_setiov(int bmd,bm_io_t * iop)7472654012fSReza Sabdar bm_setiov(int bmd, bm_io_t *iop)
7482654012fSReza Sabdar {
7492654012fSReza Sabdar 	int i;
7502654012fSReza Sabdar 	int rv;
7512654012fSReza Sabdar 	bm_iovec_t *vp;
7522654012fSReza Sabdar 	bitmap_t *bmp;
7532654012fSReza Sabdar 
7542654012fSReza Sabdar 	if (!iop)
7552654012fSReza Sabdar 		rv = -EINVAL;
7562654012fSReza Sabdar 	else if (!(bmp = bmd2bmp(bmd)))
7572654012fSReza Sabdar 		rv = -EINVAL;
7582654012fSReza Sabdar 	else if (iop->bmio_iovcnt <= 0)
7592654012fSReza Sabdar 		rv = -EINVAL;
7602654012fSReza Sabdar 	else if (!iop->bmio_iov)
7612654012fSReza Sabdar 		rv = -EINVAL;
7622654012fSReza Sabdar 	else {
7632654012fSReza Sabdar 		rv = 0;
7642654012fSReza Sabdar 		vp = iop->bmio_iov;
7652654012fSReza Sabdar 		for (i = 0; i < iop->bmio_iovcnt; vp++, i++)
7662654012fSReza Sabdar 			rv |= bmp_setval(bmp, vp);
7672654012fSReza Sabdar 	}
7682654012fSReza Sabdar 
7692654012fSReza Sabdar 	return (rv);
7702654012fSReza Sabdar }
7712654012fSReza Sabdar 
7722654012fSReza Sabdar 
7732654012fSReza Sabdar /*
7742654012fSReza Sabdar  * bmd2dbmp
7752654012fSReza Sabdar  *
7762654012fSReza Sabdar  * Convert bitmap descriptor to bitmap pointer.
7772654012fSReza Sabdar  */
7782654012fSReza Sabdar static dbitmap_t *
bmd2dbmp(int bmd)7792654012fSReza Sabdar bmd2dbmp(int bmd)
7802654012fSReza Sabdar {
7812654012fSReza Sabdar 	if (bmd < 0 || bmd >= BMAP_MAX)
7822654012fSReza Sabdar 		return (NULL);
7832654012fSReza Sabdar 
7842654012fSReza Sabdar 	return (&dbitmap[bmd]);
7852654012fSReza Sabdar }
7862654012fSReza Sabdar 
7872654012fSReza Sabdar 
7882654012fSReza Sabdar /*
7892654012fSReza Sabdar  * dbmp2bmd
7902654012fSReza Sabdar  *
7912654012fSReza Sabdar  * Convert bitmap pointer to bitmap descriptor.
7922654012fSReza Sabdar  */
7932654012fSReza Sabdar static int
dbmp2bmd(dbitmap_t * bmp)7942654012fSReza Sabdar dbmp2bmd(dbitmap_t *bmp)
7952654012fSReza Sabdar {
7962654012fSReza Sabdar 	int bmd;
7972654012fSReza Sabdar 
7982654012fSReza Sabdar 	bmd = bmp - dbitmap;
7992654012fSReza Sabdar 	if (bmd < 0 || bmd >= BMAP_MAX)
8002654012fSReza Sabdar 		bmd = -1;
8012654012fSReza Sabdar 
8022654012fSReza Sabdar 	return (bmd);
8032654012fSReza Sabdar }
8042654012fSReza Sabdar 
8052654012fSReza Sabdar /*
8062654012fSReza Sabdar  * dbmd_alloc
8072654012fSReza Sabdar  *
8082654012fSReza Sabdar  * Allocate a bitmap descriptor.
8092654012fSReza Sabdar  * Sets the INUSE flag of the slot.
8102654012fSReza Sabdar  */
8112654012fSReza Sabdar static int
dbmd_alloc(void)8122654012fSReza Sabdar dbmd_alloc(void)
8132654012fSReza Sabdar {
8142654012fSReza Sabdar 	int i;
8152654012fSReza Sabdar 	dbitmap_t *bmp;
8162654012fSReza Sabdar 
8172654012fSReza Sabdar 	bmp = dbitmap;
8182654012fSReza Sabdar 	for (i = 0; i < BMAP_MAX; bmp++, i++)
8192654012fSReza Sabdar 		if (!BMAP_IS_INUSE(bmp)) {
8202654012fSReza Sabdar 			BMAP_SET_FLAGS(bmp, BMAP_INUSE);
8212654012fSReza Sabdar 			return (i);
8222654012fSReza Sabdar 		}
8232654012fSReza Sabdar 
8242654012fSReza Sabdar 	return (-1);
8252654012fSReza Sabdar }
8262654012fSReza Sabdar 
8272654012fSReza Sabdar 
8282654012fSReza Sabdar /*
8292654012fSReza Sabdar  * dbmd_free
8302654012fSReza Sabdar  *
8312654012fSReza Sabdar  * Free a bitmap descriptor.
8322654012fSReza Sabdar  * Clears the INUSE flag of the slot.
8332654012fSReza Sabdar  */
8342654012fSReza Sabdar static void
dbmd_free(int bmd)8352654012fSReza Sabdar dbmd_free(int bmd)
8362654012fSReza Sabdar {
8372654012fSReza Sabdar 	dbitmap_t *bmp;
8382654012fSReza Sabdar 
8392654012fSReza Sabdar 	bmp = bmd2dbmp(bmd);
8402654012fSReza Sabdar 	if (bmp)
8412654012fSReza Sabdar 		BMAP_UNSET_FLAGS(bmp, BMAP_INUSE);
8422654012fSReza Sabdar }
8432654012fSReza Sabdar 
8442654012fSReza Sabdar 
8452654012fSReza Sabdar /*
8462654012fSReza Sabdar  * dbmp_set
8472654012fSReza Sabdar  *
8482654012fSReza Sabdar  * Generic function to set bit in a chunk.  This can
8492654012fSReza Sabdar  * set or unset the specified bit.
8502654012fSReza Sabdar  */
8512654012fSReza Sabdar static inline int
dbmp_set(dbmap_chunk_t * cp,u_quad_t bn,uint_t * vp)8522654012fSReza Sabdar dbmp_set(dbmap_chunk_t *cp, u_quad_t bn, uint_t *vp)
8532654012fSReza Sabdar {
8542654012fSReza Sabdar 	int rv;
8552654012fSReza Sabdar 	uint_t mask;
8562654012fSReza Sabdar 	uint_t *ip;
8572654012fSReza Sabdar 	uint_t v;
8582654012fSReza Sabdar 
8592654012fSReza Sabdar 	bn -= cp->c_off;
8602654012fSReza Sabdar 	if (bn < cp->c_clen) {
8612654012fSReza Sabdar 		mask = 1 <<(bn & BMAP_BPW_MASK);
8622654012fSReza Sabdar 		ip = &cp->c_bmp[bn >> BMAP_BPW_SHIFT];
8632654012fSReza Sabdar 		v = (*vp <<(bn & BMAP_BPW_MASK)) & mask;
8642654012fSReza Sabdar 		*ip = (*ip & ~mask) | v;
8652654012fSReza Sabdar 		BMAP_CSET_DIRTY(cp);
8662654012fSReza Sabdar 		rv = 0;
8672654012fSReza Sabdar 	} else
8682654012fSReza Sabdar 		rv = -ERANGE;
8692654012fSReza Sabdar 
8702654012fSReza Sabdar 	return (rv);
8712654012fSReza Sabdar }
8722654012fSReza Sabdar 
8732654012fSReza Sabdar 
8742654012fSReza Sabdar /*
8752654012fSReza Sabdar  * dbmp_getlen
8762654012fSReza Sabdar  *
8772654012fSReza Sabdar  * Get length of the bitmap.
8782654012fSReza Sabdar  */
8792654012fSReza Sabdar static u_quad_t
dbmp_getlen(dbitmap_t * bmp)8802654012fSReza Sabdar dbmp_getlen(dbitmap_t *bmp)
8812654012fSReza Sabdar {
8822654012fSReza Sabdar 	return (bmp ? bmp->bm_len : 0LL);
8832654012fSReza Sabdar }
8842654012fSReza Sabdar 
8852654012fSReza Sabdar 
8862654012fSReza Sabdar /*
8872654012fSReza Sabdar  * dbmp_get
8882654012fSReza Sabdar  *
8892654012fSReza Sabdar  * Generic function to get bit in a chunk.
8902654012fSReza Sabdar  */
8912654012fSReza Sabdar static inline int
dbmp_get(dbmap_chunk_t * cp,u_quad_t bn)8922654012fSReza Sabdar dbmp_get(dbmap_chunk_t *cp, u_quad_t bn)
8932654012fSReza Sabdar {
8942654012fSReza Sabdar 	int rv;
8952654012fSReza Sabdar 	uint_t bit;
8962654012fSReza Sabdar 
8972654012fSReza Sabdar 	bn -= cp->c_off;
8982654012fSReza Sabdar 	if (bn < cp->c_clen) {
8992654012fSReza Sabdar 		bit = 1 <<(bn & BMAP_BPW_MASK);
9002654012fSReza Sabdar 		rv = (cp->c_bmp[bn >> BMAP_BPW_SHIFT] & bit) != 0;
9012654012fSReza Sabdar 	} else
9022654012fSReza Sabdar 		rv = -ERANGE;
9032654012fSReza Sabdar 
9042654012fSReza Sabdar 	return (rv);
9052654012fSReza Sabdar }
9062654012fSReza Sabdar 
9072654012fSReza Sabdar 
9082654012fSReza Sabdar /*
9092654012fSReza Sabdar  * dbm_chunk_seek
9102654012fSReza Sabdar  *
9112654012fSReza Sabdar  * Seek in the file where the chunk is saved or should be saved.
9122654012fSReza Sabdar  */
9132654012fSReza Sabdar static int
dbm_chunk_seek(dbitmap_t * bmp,u_quad_t bn)9142654012fSReza Sabdar dbm_chunk_seek(dbitmap_t *bmp, u_quad_t bn)
9152654012fSReza Sabdar {
9162654012fSReza Sabdar 	int rv;
9172654012fSReza Sabdar 	off_t off;
9182654012fSReza Sabdar 
9192654012fSReza Sabdar 	if (!bmp)
9202654012fSReza Sabdar 		rv = -1;
9212654012fSReza Sabdar 	else {
9222654012fSReza Sabdar 		off = BMAP_CHUNK_NO(bn) * BMAP_CHUNK_BYTES;
9232654012fSReza Sabdar 		rv = (lseek(bmp->bm_fd, off, SEEK_SET) != off) ? -1 : 0;
9242654012fSReza Sabdar 	}
9252654012fSReza Sabdar 
9262654012fSReza Sabdar 	return (rv);
9272654012fSReza Sabdar }
9282654012fSReza Sabdar 
9292654012fSReza Sabdar 
9302654012fSReza Sabdar /*
9312654012fSReza Sabdar  * dbm_chunk_flush
9322654012fSReza Sabdar  *
9332654012fSReza Sabdar  * Save a chunk to file.
9342654012fSReza Sabdar  */
9352654012fSReza Sabdar static int
dbm_chunk_flush(dbitmap_t * bmp,dbmap_chunk_t * cp)9362654012fSReza Sabdar dbm_chunk_flush(dbitmap_t *bmp, dbmap_chunk_t *cp)
9372654012fSReza Sabdar {
9382654012fSReza Sabdar 	int rv;
9392654012fSReza Sabdar 
9402654012fSReza Sabdar 	bitmap_stats.bs_chunk_flush++;
9412654012fSReza Sabdar 	if (!bmp || !cp)
9422654012fSReza Sabdar 		rv = -1;
9432654012fSReza Sabdar 	else if (dbm_chunk_seek(bmp, cp->c_off) != 0)
9442654012fSReza Sabdar 		rv = -1;
9452654012fSReza Sabdar 	else if (write(bmp->bm_fd, cp->c_bmp, cp->c_mlen) != cp->c_mlen)
9462654012fSReza Sabdar 		rv = -1;
9472654012fSReza Sabdar 	else
9482654012fSReza Sabdar 		rv = 0;
9492654012fSReza Sabdar 
9502654012fSReza Sabdar 	return (rv);
9512654012fSReza Sabdar }
9522654012fSReza Sabdar 
9532654012fSReza Sabdar 
9542654012fSReza Sabdar /*
9552654012fSReza Sabdar  * dbm_chunk_load
9562654012fSReza Sabdar  *
9572654012fSReza Sabdar  * Load a chunk from a file.  If the chunk is a new one,
9582654012fSReza Sabdar  * instead of reading from the disk, the memory for the
9592654012fSReza Sabdar  * chunk is set to either all zeros or to all ones.
9602654012fSReza Sabdar  * Otherwise, if the chunk is not a new one, it's read
9612654012fSReza Sabdar  * from the disk.
9622654012fSReza Sabdar  *
9632654012fSReza Sabdar  * The new chunk is positioned in the LRU and hash table
9642654012fSReza Sabdar  * after its data is ready.
9652654012fSReza Sabdar  */
9662654012fSReza Sabdar static dbmap_chunk_t *
dbm_chunk_load(dbitmap_t * bmp,dbmap_chunk_t * cp,u_quad_t bn,int new)9672654012fSReza Sabdar dbm_chunk_load(dbitmap_t *bmp, dbmap_chunk_t *cp, u_quad_t bn, int new)
9682654012fSReza Sabdar {
9692654012fSReza Sabdar 	int h;
9702654012fSReza Sabdar 	u_quad_t off, l;
9712654012fSReza Sabdar 	uint_t cl, ml;
9722654012fSReza Sabdar 	dbmap_list_t *hp;
9732654012fSReza Sabdar 
9742654012fSReza Sabdar 	off = BMAP_CHUNK_OFF(bn);
9752654012fSReza Sabdar 	l = bmp->bm_len - off;
9762654012fSReza Sabdar 	if (l >= BMAP_CHUNK_BITS) {
9772654012fSReza Sabdar 		cl = BMAP_CHUNK_BITS;
9782654012fSReza Sabdar 		ml = BMAP_CHUNK_BYTES;
9792654012fSReza Sabdar 	} else {
9802654012fSReza Sabdar 		cl = l;
9812654012fSReza Sabdar 		ml = MEM_LEN(l);
9822654012fSReza Sabdar 	}
9832654012fSReza Sabdar 
9842654012fSReza Sabdar 	if (new == BMAP_NEW_CHUNK) {
9852654012fSReza Sabdar 		if (BMAP_IS_INIT_ONES(bmp))
9862654012fSReza Sabdar 			(void) memset(cp->c_bmp, 0xff, ml);
9872654012fSReza Sabdar 		else
9882654012fSReza Sabdar 			(void) memset(cp->c_bmp, 0x00, ml);
9892654012fSReza Sabdar 	} else { /* BMAP_OLD_CHUNK */
9902654012fSReza Sabdar 		if (dbm_chunk_seek(bmp, bn) != 0)
9912654012fSReza Sabdar 			cp = NULL;
9922654012fSReza Sabdar 		else if (read(bmp->bm_fd, cp->c_bmp, ml) != ml)
9932654012fSReza Sabdar 			cp = NULL;
9942654012fSReza Sabdar 	}
9952654012fSReza Sabdar 
9962654012fSReza Sabdar 	if (cp) {
9972654012fSReza Sabdar 		TAILQ_INSERT_TAIL(&bmp->bm_lru, cp, c_lru);
9982654012fSReza Sabdar 		h = HASH(bn);
9992654012fSReza Sabdar 		hp = &bmp->bm_hash[h];
10002654012fSReza Sabdar 		TAILQ_INSERT_HEAD(hp, cp, c_hash);
10012654012fSReza Sabdar 		cp->c_flags = 0;
10022654012fSReza Sabdar 		cp->c_off = off;
10032654012fSReza Sabdar 		cp->c_clen = cl;
10042654012fSReza Sabdar 		cp->c_mlen = ml;
10052654012fSReza Sabdar 	}
10062654012fSReza Sabdar 
10072654012fSReza Sabdar 	return (cp);
10082654012fSReza Sabdar }
10092654012fSReza Sabdar 
10102654012fSReza Sabdar 
10112654012fSReza Sabdar /*
10122654012fSReza Sabdar  * dbm_chunk_new
10132654012fSReza Sabdar  *
10142654012fSReza Sabdar  * Create a new chunk and keep track of memory used.
10152654012fSReza Sabdar  */
10162654012fSReza Sabdar static dbmap_chunk_t *
dbm_chunk_new(dbitmap_t * bmp,u_quad_t bn)10172654012fSReza Sabdar dbm_chunk_new(dbitmap_t *bmp, u_quad_t bn)
10182654012fSReza Sabdar {
10192654012fSReza Sabdar 	dbmap_chunk_t *cp;
10202654012fSReza Sabdar 
10212654012fSReza Sabdar 	bitmap_stats.bs_chunk_new++;
10222654012fSReza Sabdar 	cp = ndmp_malloc(sizeof (dbmap_chunk_t));
10232654012fSReza Sabdar 	if (cp) {
10242654012fSReza Sabdar 		cp->c_bmp = ndmp_malloc(sizeof (uint_t) * BMAP_CHUNK_WORDS);
10252654012fSReza Sabdar 		if (!cp->c_bmp) {
10262654012fSReza Sabdar 			free(cp);
10272654012fSReza Sabdar 			cp = NULL;
10282654012fSReza Sabdar 		} else if (!dbm_chunk_load(bmp, cp, bn, BMAP_NEW_CHUNK)) {
10292654012fSReza Sabdar 			free(cp->c_bmp);
10302654012fSReza Sabdar 			free(cp);
10312654012fSReza Sabdar 			cp = NULL;
10322654012fSReza Sabdar 		} else
10332654012fSReza Sabdar 			bmp->bm_ccur++;
10342654012fSReza Sabdar 	}
10352654012fSReza Sabdar 
10362654012fSReza Sabdar 	return (cp);
10372654012fSReza Sabdar }
10382654012fSReza Sabdar 
10392654012fSReza Sabdar 
10402654012fSReza Sabdar /*
10412654012fSReza Sabdar  * dbm_chunk_alloc
10422654012fSReza Sabdar  *
10432654012fSReza Sabdar  * Allocate a chunk and return it.  If the cache for the
10442654012fSReza Sabdar  * chunks is not fully used, a new chunk is created.
10452654012fSReza Sabdar  * Otherwise, the first chunk from the LRU list is reclaimed,
10462654012fSReza Sabdar  * loaded and returned.
10472654012fSReza Sabdar  */
10482654012fSReza Sabdar static dbmap_chunk_t *
dbm_chunk_alloc(dbitmap_t * bmp,u_quad_t bn)10492654012fSReza Sabdar dbm_chunk_alloc(dbitmap_t *bmp, u_quad_t bn)
10502654012fSReza Sabdar {
10512654012fSReza Sabdar 	int h;
10522654012fSReza Sabdar 	dbmap_list_t *hp;
10532654012fSReza Sabdar 	dbmap_chunk_t *cp;
10542654012fSReza Sabdar 
10552654012fSReza Sabdar 	if (bmp->bm_ccur < bmp->bm_cmax)
10562654012fSReza Sabdar 		return (dbm_chunk_new(bmp, bn));
10572654012fSReza Sabdar 
10582654012fSReza Sabdar 	bitmap_stats.bs_chunk_reclaim++;
10592654012fSReza Sabdar 
10602654012fSReza Sabdar 	cp = TAILQ_FIRST(&bmp->bm_lru);
10612654012fSReza Sabdar 	if (BMAP_CIS_DIRTY(cp))
10622654012fSReza Sabdar 		(void) dbm_chunk_flush(bmp, cp);
10632654012fSReza Sabdar 
10642654012fSReza Sabdar 	TAILQ_REMOVE(&bmp->bm_lru, cp, c_lru);
10652654012fSReza Sabdar 	h = HASH(cp->c_off);
10662654012fSReza Sabdar 	hp = &bmp->bm_hash[h];
10672654012fSReza Sabdar 	TAILQ_REMOVE(hp, cp, c_hash);
10682654012fSReza Sabdar 	return (dbm_chunk_load(bmp, cp, bn, BMAP_OLD_CHUNK));
10692654012fSReza Sabdar }
10702654012fSReza Sabdar 
10712654012fSReza Sabdar 
10722654012fSReza Sabdar /*
10732654012fSReza Sabdar  * dbm_chunks_free
10742654012fSReza Sabdar  *
10752654012fSReza Sabdar  * Release the memory allocated for the chunks.
10762654012fSReza Sabdar  */
10772654012fSReza Sabdar static void
dbm_chunks_free(dbitmap_t * bmp)10782654012fSReza Sabdar dbm_chunks_free(dbitmap_t *bmp)
10792654012fSReza Sabdar {
10802654012fSReza Sabdar 	dbmap_list_t *headp;
10812654012fSReza Sabdar 	dbmap_chunk_t *cp;
10822654012fSReza Sabdar 
10832654012fSReza Sabdar 	if (!bmp)
10842654012fSReza Sabdar 		return;
10852654012fSReza Sabdar 
10862654012fSReza Sabdar 	headp = &bmp->bm_lru;
10872654012fSReza Sabdar 	if (!headp)
10882654012fSReza Sabdar 		return;
10892654012fSReza Sabdar 
10902654012fSReza Sabdar 	while (!TAILQ_EMPTY(headp)) {
10912654012fSReza Sabdar 		cp = TAILQ_FIRST(headp);
10922654012fSReza Sabdar 		TAILQ_REMOVE(headp, cp, c_lru);
10932654012fSReza Sabdar 		free(cp->c_bmp);
10942654012fSReza Sabdar 		free(cp);
10952654012fSReza Sabdar 	}
10962654012fSReza Sabdar }
10972654012fSReza Sabdar 
10982654012fSReza Sabdar 
10992654012fSReza Sabdar /*
11002654012fSReza Sabdar  * dbm_chunk_reposition
11012654012fSReza Sabdar  *
11022654012fSReza Sabdar  * Re-position the chunk in the LRU and the hash table.
11032654012fSReza Sabdar  */
11042654012fSReza Sabdar static void
dbm_chunk_reposition(dbitmap_t * bmp,dbmap_list_t * hp,dbmap_chunk_t * cp)11052654012fSReza Sabdar dbm_chunk_reposition(dbitmap_t *bmp, dbmap_list_t *hp, dbmap_chunk_t *cp)
11062654012fSReza Sabdar {
11072654012fSReza Sabdar 	if (bmp && hp && cp) {
11082654012fSReza Sabdar 		TAILQ_REMOVE(&bmp->bm_lru, cp, c_lru);
11092654012fSReza Sabdar 		TAILQ_INSERT_TAIL(&bmp->bm_lru, cp, c_lru);
11102654012fSReza Sabdar 		if (TAILQ_FIRST(hp) != cp) {
11112654012fSReza Sabdar 			TAILQ_REMOVE(hp, cp, c_hash);
11122654012fSReza Sabdar 			TAILQ_INSERT_HEAD(hp, cp, c_hash);
11132654012fSReza Sabdar 		}
11142654012fSReza Sabdar 	}
11152654012fSReza Sabdar }
11162654012fSReza Sabdar 
11172654012fSReza Sabdar 
11182654012fSReza Sabdar /*
11192654012fSReza Sabdar  * dbm_chunk_find
11202654012fSReza Sabdar  *
11212654012fSReza Sabdar  * Find and return the chunks which holds the specified bit.
11222654012fSReza Sabdar  * Allocate the chunk if necessary and re-position it in the
11232654012fSReza Sabdar  * LRU and hash table lists.
11242654012fSReza Sabdar  */
11252654012fSReza Sabdar static dbmap_chunk_t *
dbm_chunk_find(dbitmap_t * bmp,u_quad_t bn)11262654012fSReza Sabdar dbm_chunk_find(dbitmap_t *bmp, u_quad_t bn)
11272654012fSReza Sabdar {
11282654012fSReza Sabdar 	int h;
11292654012fSReza Sabdar 	dbmap_chunk_t *cp;
11302654012fSReza Sabdar 	dbmap_list_t *hp;
11312654012fSReza Sabdar 
11322654012fSReza Sabdar 	if (!bmp)
11332654012fSReza Sabdar 		return (NULL);
11342654012fSReza Sabdar 
11352654012fSReza Sabdar 	h = HASH(bn);
11362654012fSReza Sabdar 	hp = &bmp->bm_hash[h];
11372654012fSReza Sabdar 	TAILQ_FOREACH(cp, hp, c_hash) {
11382654012fSReza Sabdar 		if (bn >= cp->c_off && bn < (cp->c_off + cp->c_clen)) {
11392654012fSReza Sabdar 			bitmap_stats.bs_cache_hit++;
11402654012fSReza Sabdar 
11412654012fSReza Sabdar 			dbm_chunk_reposition(bmp, hp, cp);
11422654012fSReza Sabdar 			return (cp);
11432654012fSReza Sabdar 		}
11442654012fSReza Sabdar 	}
11452654012fSReza Sabdar 
11462654012fSReza Sabdar 	bitmap_stats.bs_cache_miss++;
11472654012fSReza Sabdar 
11482654012fSReza Sabdar 	return (dbm_chunk_alloc(bmp, bn));
11492654012fSReza Sabdar }
11502654012fSReza Sabdar 
11512654012fSReza Sabdar 
11522654012fSReza Sabdar /*
11532654012fSReza Sabdar  * dbmp_setval
11542654012fSReza Sabdar  *
11552654012fSReza Sabdar  * Set a range of bits in the bitmap specified by the
11562654012fSReza Sabdar  * vector.
11572654012fSReza Sabdar  */
11582654012fSReza Sabdar static int
dbmp_setval(dbitmap_t * bmp,bm_iovec_t * vp)11592654012fSReza Sabdar dbmp_setval(dbitmap_t *bmp, bm_iovec_t *vp)
11602654012fSReza Sabdar {
11612654012fSReza Sabdar 	int rv;
11622654012fSReza Sabdar 	u_quad_t cl;
11632654012fSReza Sabdar 	u_quad_t bn;
11642654012fSReza Sabdar 	u_quad_t max;
11652654012fSReza Sabdar 	dbmap_chunk_t *cp;
11662654012fSReza Sabdar 
11672654012fSReza Sabdar 	bn = vp->bmv_base;
11682654012fSReza Sabdar 	max = bn + vp->bmv_len;
11692654012fSReza Sabdar 	if (bn >= bmp->bm_len || max > bmp->bm_len)
11702654012f