1// SPDX-License-Identifier: GPL-2.0-only
   2/*
   3 * lib/bitmap.c
   4 * Helper functions for bitmap.h.
 
 
 
   5 */
   6
   7#include <linux/bitmap.h>
   8#include <linux/bitops.h>
   9#include <linux/bug.h>
  10#include <linux/ctype.h>
  11#include <linux/device.h>
  12#include <linux/errno.h>
  13#include <linux/export.h>
  14#include <linux/kernel.h>
  15#include <linux/mm.h>
  16#include <linux/slab.h>
  17#include <linux/string.h>
  18#include <linux/thread_info.h>
  19#include <linux/uaccess.h>
  20
  21#include <asm/page.h>
  22
  23#include "kstrtox.h"
  24
  25/**
  26 * DOC: bitmap introduction
  27 *
  28 * bitmaps provide an array of bits, implemented using an
  29 * array of unsigned longs.  The number of valid bits in a
  30 * given bitmap does _not_ need to be an exact multiple of
  31 * BITS_PER_LONG.
  32 *
  33 * The possible unused bits in the last, partially used word
  34 * of a bitmap are 'don't care'.  The implementation makes
  35 * no particular effort to keep them zero.  It ensures that
  36 * their value will not affect the results of any operation.
  37 * The bitmap operations that return Boolean (bitmap_empty,
  38 * for example) or scalar (bitmap_weight, for example) results
  39 * carefully filter out these unused bits from impacting their
  40 * results.
  41 *
 
 
 
 
 
  42 * The byte ordering of bitmaps is more natural on little
  43 * endian architectures.  See the big-endian headers
  44 * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
  45 * for the best explanations of this ordering.
  46 */
  47
  48int __bitmap_equal(const unsigned long *bitmap1,
  49		const unsigned long *bitmap2, unsigned int bits)
  50{
  51	unsigned int k, lim = bits/BITS_PER_LONG;
  52	for (k = 0; k < lim; ++k)
  53		if (bitmap1[k] != bitmap2[k])
  54			return 0;
  55
  56	if (bits % BITS_PER_LONG)
  57		if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
  58			return 0;
  59
  60	return 1;
  61}
  62EXPORT_SYMBOL(__bitmap_equal);
  63
  64bool __bitmap_or_equal(const unsigned long *bitmap1,
  65		       const unsigned long *bitmap2,
  66		       const unsigned long *bitmap3,
  67		       unsigned int bits)
  68{
  69	unsigned int k, lim = bits / BITS_PER_LONG;
  70	unsigned long tmp;
  71
  72	for (k = 0; k < lim; ++k) {
  73		if ((bitmap1[k] | bitmap2[k]) != bitmap3[k])
  74			return false;
  75	}
  76
  77	if (!(bits % BITS_PER_LONG))
  78		return true;
 
  79
  80	tmp = (bitmap1[k] | bitmap2[k]) ^ bitmap3[k];
  81	return (tmp & BITMAP_LAST_WORD_MASK(bits)) == 0;
  82}
 
  83
  84void __bitmap_complement(unsigned long *dst, const unsigned long *src, unsigned int bits)
 
  85{
  86	unsigned int k, lim = BITS_TO_LONGS(bits);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
  87	for (k = 0; k < lim; ++k)
  88		dst[k] = ~src[k];
 
 
 
  89}
  90EXPORT_SYMBOL(__bitmap_complement);
  91
  92/**
  93 * __bitmap_shift_right - logical right shift of the bits in a bitmap
  94 *   @dst : destination bitmap
  95 *   @src : source bitmap
  96 *   @shift : shift by this many bits
  97 *   @nbits : bitmap size, in bits
  98 *
  99 * Shifting right (dividing) means moving bits in the MS -> LS bit
 100 * direction.  Zeros are fed into the vacated MS positions and the
 101 * LS bits shifted off the bottom are lost.
 102 */
 103void __bitmap_shift_right(unsigned long *dst, const unsigned long *src,
 104			unsigned shift, unsigned nbits)
 105{
 106	unsigned k, lim = BITS_TO_LONGS(nbits);
 107	unsigned off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
 108	unsigned long mask = BITMAP_LAST_WORD_MASK(nbits);
 109	for (k = 0; off + k < lim; ++k) {
 110		unsigned long upper, lower;
 111
 112		/*
 113		 * If shift is not word aligned, take lower rem bits of
 114		 * word above and make them the top rem bits of result.
 115		 */
 116		if (!rem || off + k + 1 >= lim)
 117			upper = 0;
 118		else {
 119			upper = src[off + k + 1];
 120			if (off + k + 1 == lim - 1)
 121				upper &= mask;
 122			upper <<= (BITS_PER_LONG - rem);
 123		}
 124		lower = src[off + k];
 125		if (off + k == lim - 1)
 126			lower &= mask;
 127		lower >>= rem;
 128		dst[k] = lower | upper;
 
 129	}
 130	if (off)
 131		memset(&dst[lim - off], 0, off*sizeof(unsigned long));
 132}
 133EXPORT_SYMBOL(__bitmap_shift_right);
 134
 135
 136/**
 137 * __bitmap_shift_left - logical left shift of the bits in a bitmap
 138 *   @dst : destination bitmap
 139 *   @src : source bitmap
 140 *   @shift : shift by this many bits
 141 *   @nbits : bitmap size, in bits
 142 *
 143 * Shifting left (multiplying) means moving bits in the LS -> MS
 144 * direction.  Zeros are fed into the vacated LS bit positions
 145 * and those MS bits shifted off the top are lost.
 146 */
 147
 148void __bitmap_shift_left(unsigned long *dst, const unsigned long *src,
 149			unsigned int shift, unsigned int nbits)
 150{
 151	int k;
 152	unsigned int lim = BITS_TO_LONGS(nbits);
 153	unsigned int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
 154	for (k = lim - off - 1; k >= 0; --k) {
 155		unsigned long upper, lower;
 156
 157		/*
 158		 * If shift is not word aligned, take upper rem bits of
 159		 * word below and make them the bottom rem bits of result.
 160		 */
 161		if (rem && k > 0)
 162			lower = src[k - 1] >> (BITS_PER_LONG - rem);
 163		else
 164			lower = 0;
 165		upper = src[k] << rem;
 166		dst[k + off] = lower | upper;
 
 
 
 
 167	}
 168	if (off)
 169		memset(dst, 0, off*sizeof(unsigned long));
 170}
 171EXPORT_SYMBOL(__bitmap_shift_left);
 172
 173/**
 174 * bitmap_cut() - remove bit region from bitmap and right shift remaining bits
 175 * @dst: destination bitmap, might overlap with src
 176 * @src: source bitmap
 177 * @first: start bit of region to be removed
 178 * @cut: number of bits to remove
 179 * @nbits: bitmap size, in bits
 180 *
 181 * Set the n-th bit of @dst iff the n-th bit of @src is set and
 182 * n is less than @first, or the m-th bit of @src is set for any
 183 * m such that @first <= n < nbits, and m = n + @cut.
 184 *
 185 * In pictures, example for a big-endian 32-bit architecture:
 186 *
 187 * The @src bitmap is::
 188 *
 189 *   31                                   63
 190 *   |                                    |
 191 *   10000000 11000001 11110010 00010101  10000000 11000001 01110010 00010101
 192 *                   |  |              |                                    |
 193 *                  16  14             0                                   32
 194 *
 195 * if @cut is 3, and @first is 14, bits 14-16 in @src are cut and @dst is::
 196 *
 197 *   31                                   63
 198 *   |                                    |
 199 *   10110000 00011000 00110010 00010101  00010000 00011000 00101110 01000010
 200 *                      |              |                                    |
 201 *                      14 (bit 17     0                                   32
 202 *                          from @src)
 203 *
 204 * Note that @dst and @src might overlap partially or entirely.
 205 *
 206 * This is implemented in the obvious way, with a shift and carry
 207 * step for each moved bit. Optimisation is left as an exercise
 208 * for the compiler.
 209 */
 210void bitmap_cut(unsigned long *dst, const unsigned long *src,
 211		unsigned int first, unsigned int cut, unsigned int nbits)
 212{
 213	unsigned int len = BITS_TO_LONGS(nbits);
 214	unsigned long keep = 0, carry;
 215	int i;
 216
 217	if (first % BITS_PER_LONG) {
 218		keep = src[first / BITS_PER_LONG] &
 219		       (~0UL >> (BITS_PER_LONG - first % BITS_PER_LONG));
 220	}
 221
 222	memmove(dst, src, len * sizeof(*dst));
 223
 224	while (cut--) {
 225		for (i = first / BITS_PER_LONG; i < len; i++) {
 226			if (i < len - 1)
 227				carry = dst[i + 1] & 1UL;
 228			else
 229				carry = 0;
 230
 231			dst[i] = (dst[i] >> 1) | (carry << (BITS_PER_LONG - 1));
 232		}
 233	}
 234
 235	dst[first / BITS_PER_LONG] &= ~0UL << (first % BITS_PER_LONG);
 236	dst[first / BITS_PER_LONG] |= keep;
 237}
 238EXPORT_SYMBOL(bitmap_cut);
 239
 240int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
 241				const unsigned long *bitmap2, unsigned int bits)
 242{
 243	unsigned int k;
 244	unsigned int lim = bits/BITS_PER_LONG;
 245	unsigned long result = 0;
 246
 247	for (k = 0; k < lim; k++)
 248		result |= (dst[k] = bitmap1[k] & bitmap2[k]);
 249	if (bits % BITS_PER_LONG)
 250		result |= (dst[k] = bitmap1[k] & bitmap2[k] &
 251			   BITMAP_LAST_WORD_MASK(bits));
 252	return result != 0;
 253}
 254EXPORT_SYMBOL(__bitmap_and);
 255
 256void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
 257				const unsigned long *bitmap2, unsigned int bits)
 258{
 259	unsigned int k;
 260	unsigned int nr = BITS_TO_LONGS(bits);
 261
 262	for (k = 0; k < nr; k++)
 263		dst[k] = bitmap1[k] | bitmap2[k];
 264}
 265EXPORT_SYMBOL(__bitmap_or);
 266
 267void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
 268				const unsigned long *bitmap2, unsigned int bits)
 269{
 270	unsigned int k;
 271	unsigned int nr = BITS_TO_LONGS(bits);
 272
 273	for (k = 0; k < nr; k++)
 274		dst[k] = bitmap1[k] ^ bitmap2[k];
 275}
 276EXPORT_SYMBOL(__bitmap_xor);
 277
 278int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
 279				const unsigned long *bitmap2, unsigned int bits)
 280{
 281	unsigned int k;
 282	unsigned int lim = bits/BITS_PER_LONG;
 283	unsigned long result = 0;
 284
 285	for (k = 0; k < lim; k++)
 286		result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
 287	if (bits % BITS_PER_LONG)
 288		result |= (dst[k] = bitmap1[k] & ~bitmap2[k] &
 289			   BITMAP_LAST_WORD_MASK(bits));
 290	return result != 0;
 291}
 292EXPORT_SYMBOL(__bitmap_andnot);
 293
 294void __bitmap_replace(unsigned long *dst,
 295		      const unsigned long *old, const unsigned long *new,
 296		      const unsigned long *mask, unsigned int nbits)
 297{
 298	unsigned int k;
 299	unsigned int nr = BITS_TO_LONGS(nbits);
 300
 301	for (k = 0; k < nr; k++)
 302		dst[k] = (old[k] & ~mask[k]) | (new[k] & mask[k]);
 303}
 304EXPORT_SYMBOL(__bitmap_replace);
 305
 306int __bitmap_intersects(const unsigned long *bitmap1,
 307			const unsigned long *bitmap2, unsigned int bits)
 308{
 309	unsigned int k, lim = bits/BITS_PER_LONG;
 310	for (k = 0; k < lim; ++k)
 311		if (bitmap1[k] & bitmap2[k])
 312			return 1;
 313
 314	if (bits % BITS_PER_LONG)
 315		if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
 316			return 1;
 317	return 0;
 318}
 319EXPORT_SYMBOL(__bitmap_intersects);
 320
 321int __bitmap_subset(const unsigned long *bitmap1,
 322		    const unsigned long *bitmap2, unsigned int bits)
 323{
 324	unsigned int k, lim = bits/BITS_PER_LONG;
 325	for (k = 0; k < lim; ++k)
 326		if (bitmap1[k] & ~bitmap2[k])
 327			return 0;
 328
 329	if (bits % BITS_PER_LONG)
 330		if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
 331			return 0;
 332	return 1;
 333}
 334EXPORT_SYMBOL(__bitmap_subset);
 335
 336int __bitmap_weight(const unsigned long *bitmap, unsigned int bits)
 337{
 338	unsigned int k, lim = bits/BITS_PER_LONG;
 339	int w = 0;
 340
 341	for (k = 0; k < lim; k++)
 342		w += hweight_long(bitmap[k]);
 343
 344	if (bits % BITS_PER_LONG)
 345		w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
 346
 347	return w;
 348}
 349EXPORT_SYMBOL(__bitmap_weight);
 350
 351void __bitmap_set(unsigned long *map, unsigned int start, int len)
 352{
 353	unsigned long *p = map + BIT_WORD(start);
 354	const unsigned int size = start + len;
 355	int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
 356	unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
 357
 358	while (len - bits_to_set >= 0) {
 359		*p |= mask_to_set;
 360		len -= bits_to_set;
 361		bits_to_set = BITS_PER_LONG;
 362		mask_to_set = ~0UL;
 363		p++;
 364	}
 365	if (len) {
 366		mask_to_set &= BITMAP_LAST_WORD_MASK(size);
 367		*p |= mask_to_set;
 368	}
 369}
 370EXPORT_SYMBOL(__bitmap_set);
 371
 372void __bitmap_clear(unsigned long *map, unsigned int start, int len)
 373{
 374	unsigned long *p = map + BIT_WORD(start);
 375	const unsigned int size = start + len;
 376	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
 377	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
 378
 379	while (len - bits_to_clear >= 0) {
 380		*p &= ~mask_to_clear;
 381		len -= bits_to_clear;
 382		bits_to_clear = BITS_PER_LONG;
 383		mask_to_clear = ~0UL;
 384		p++;
 385	}
 386	if (len) {
 387		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
 388		*p &= ~mask_to_clear;
 389	}
 390}
 391EXPORT_SYMBOL(__bitmap_clear);
 392
 393/**
 394 * bitmap_find_next_zero_area_off - find a contiguous aligned zero area
 395 * @map: The address to base the search on
 396 * @size: The bitmap size in bits
 397 * @start: The bitnumber to start searching at
 398 * @nr: The number of zeroed bits we're looking for
 399 * @align_mask: Alignment mask for zero area
 400 * @align_offset: Alignment offset for zero area.
 401 *
 402 * The @align_mask should be one less than a power of 2; the effect is that
 403 * the bit offset of all zero areas this function finds plus @align_offset
 404 * is multiple of that power of 2.
 405 */
 406unsigned long bitmap_find_next_zero_area_off(unsigned long *map,
 407					     unsigned long size,
 408					     unsigned long start,
 409					     unsigned int nr,
 410					     unsigned long align_mask,
 411					     unsigned long align_offset)
 412{
 413	unsigned long index, end, i;
 414again:
 415	index = find_next_zero_bit(map, size, start);
 416
 417	/* Align allocation */
 418	index = __ALIGN_MASK(index + align_offset, align_mask) - align_offset;
 419
 420	end = index + nr;
 421	if (end > size)
 422		return end;
 423	i = find_next_bit(map, end, index);
 424	if (i < end) {
 425		start = i + 1;
 426		goto again;
 427	}
 428	return index;
 429}
 430EXPORT_SYMBOL(bitmap_find_next_zero_area_off);
 431
 432/*
 433 * Bitmap printing & parsing functions: first version by Nadia Yvette Chambers,
 434 * second version by Paul Jackson, third by Joe Korty.
 435 */
 436
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 437/**
 438 * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap
 439 *
 440 * @ubuf: pointer to user buffer containing string.
 441 * @ulen: buffer size in bytes.  If string is smaller than this
 442 *    then it must be terminated with a \0.
 443 * @maskp: pointer to bitmap array that will contain result.
 444 * @nmaskbits: size of bitmap, in bits.
 
 
 
 
 
 
 445 */
 446int bitmap_parse_user(const char __user *ubuf,
 447			unsigned int ulen, unsigned long *maskp,
 448			int nmaskbits)
 449{
 450	char *buf;
 451	int ret;
 452
 453	buf = memdup_user_nul(ubuf, ulen);
 454	if (IS_ERR(buf))
 455		return PTR_ERR(buf);
 456
 457	ret = bitmap_parse(buf, UINT_MAX, maskp, nmaskbits);
 458
 459	kfree(buf);
 460	return ret;
 461}
 462EXPORT_SYMBOL(bitmap_parse_user);
 463
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 464/**
 465 * bitmap_print_to_pagebuf - convert bitmap to list or hex format ASCII string
 466 * @list: indicates whether the bitmap must be list
 467 * @buf: page aligned buffer into which string is placed
 468 * @maskp: pointer to bitmap to convert
 469 * @nmaskbits: size of bitmap, in bits
 470 *
 471 * Output format is a comma-separated list of decimal numbers and
 472 * ranges if list is specified or hex digits grouped into comma-separated
 473 * sets of 8 digits/set. Returns the number of characters written to buf.
 
 
 474 *
 475 * It is assumed that @buf is a pointer into a PAGE_SIZE, page-aligned
 476 * area and that sufficient storage remains at @buf to accommodate the
 477 * bitmap_print_to_pagebuf() output. Returns the number of characters
 478 * actually printed to @buf, excluding terminating '\0'.
 479 */
 480int bitmap_print_to_pagebuf(bool list, char *buf, const unsigned long *maskp,
 481			    int nmaskbits)
 482{
 483	ptrdiff_t len = PAGE_SIZE - offset_in_page(buf);
 484
 485	return list ? scnprintf(buf, len, "%*pbl\n", nmaskbits, maskp) :
 486		      scnprintf(buf, len, "%*pb\n", nmaskbits, maskp);
 487}
 488EXPORT_SYMBOL(bitmap_print_to_pagebuf);
 489
 490/*
 491 * Region 9-38:4/10 describes the following bitmap structure:
 492 * 0	   9  12    18			38	     N
 493 * .........****......****......****..................
 494 *	    ^  ^     ^			 ^	     ^
 495 *      start  off   group_len	       end	 nbits
 496 */
 497struct region {
 498	unsigned int start;
 499	unsigned int off;
 500	unsigned int group_len;
 501	unsigned int end;
 502	unsigned int nbits;
 503};
 504
 505static void bitmap_set_region(const struct region *r, unsigned long *bitmap)
 506{
 507	unsigned int start;
 508
 509	for (start = r->start; start <= r->end; start += r->group_len)
 510		bitmap_set(bitmap, start, min(r->end - start + 1, r->off));
 511}
 512
 513static int bitmap_check_region(const struct region *r)
 514{
 515	if (r->start > r->end || r->group_len == 0 || r->off > r->group_len)
 516		return -EINVAL;
 517
 518	if (r->end >= r->nbits)
 519		return -ERANGE;
 520
 521	return 0;
 522}
 523
 524static const char *bitmap_getnum(const char *str, unsigned int *num,
 525				 unsigned int lastbit)
 526{
 527	unsigned long long n;
 528	unsigned int len;
 529
 530	if (str[0] == 'N') {
 531		*num = lastbit;
 532		return str + 1;
 533	}
 534
 535	len = _parse_integer(str, 10, &n);
 536	if (!len)
 537		return ERR_PTR(-EINVAL);
 538	if (len & KSTRTOX_OVERFLOW || n != (unsigned int)n)
 539		return ERR_PTR(-EOVERFLOW);
 540
 541	*num = n;
 542	return str + len;
 543}
 544
 545static inline bool end_of_str(char c)
 546{
 547	return c == '\0' || c == '\n';
 548}
 549
 550static inline bool __end_of_region(char c)
 551{
 552	return isspace(c) || c == ',';
 553}
 554
 555static inline bool end_of_region(char c)
 556{
 557	return __end_of_region(c) || end_of_str(c);
 558}
 559
 560/*
 561 * The format allows commas and whitespaces at the beginning
 562 * of the region.
 563 */
 564static const char *bitmap_find_region(const char *str)
 565{
 566	while (__end_of_region(*str))
 567		str++;
 568
 569	return end_of_str(*str) ? NULL : str;
 570}
 571
 572static const char *bitmap_find_region_reverse(const char *start, const char *end)
 573{
 574	while (start <= end && __end_of_region(*end))
 575		end--;
 576
 577	return end;
 578}
 579
 580static const char *bitmap_parse_region(const char *str, struct region *r)
 581{
 582	unsigned int lastbit = r->nbits - 1;
 583
 584	if (!strncasecmp(str, "all", 3)) {
 585		r->start = 0;
 586		r->end = lastbit;
 587		str += 3;
 588
 589		goto check_pattern;
 
 
 
 
 
 
 
 590	}
 591
 592	str = bitmap_getnum(str, &r->start, lastbit);
 593	if (IS_ERR(str))
 594		return str;
 595
 596	if (end_of_region(*str))
 597		goto no_end;
 598
 599	if (*str != '-')
 600		return ERR_PTR(-EINVAL);
 601
 602	str = bitmap_getnum(str + 1, &r->end, lastbit);
 603	if (IS_ERR(str))
 604		return str;
 605
 606check_pattern:
 607	if (end_of_region(*str))
 608		goto no_pattern;
 609
 610	if (*str != ':')
 611		return ERR_PTR(-EINVAL);
 612
 613	str = bitmap_getnum(str + 1, &r->off, lastbit);
 614	if (IS_ERR(str))
 615		return str;
 616
 617	if (*str != '/')
 618		return ERR_PTR(-EINVAL);
 619
 620	return bitmap_getnum(str + 1, &r->group_len, lastbit);
 621
 622no_end:
 623	r->end = r->start;
 624no_pattern:
 625	r->off = r->end + 1;
 626	r->group_len = r->end + 1;
 627
 628	return end_of_str(*str) ? NULL : str;
 629}
 
 630
 631/**
 632 * bitmap_parselist - convert list format ASCII string to bitmap
 633 * @buf: read user string from this buffer; must be terminated
 634 *    with a \0 or \n.
 
 
 635 * @maskp: write resulting mask here
 636 * @nmaskbits: number of bits in mask to be written
 637 *
 638 * Input format is a comma-separated list of decimal numbers and
 639 * ranges.  Consecutively set bits are shown as two hyphen-separated
 640 * decimal numbers, the smallest and largest bit numbers set in
 641 * the range.
 642 * Optionally each range can be postfixed to denote that only parts of it
 643 * should be set. The range will divided to groups of specific size.
 644 * From each group will be used only defined amount of bits.
 645 * Syntax: range:used_size/group_size
 646 * Example: 0-1023:2/256 ==> 0,1,256,257,512,513,768,769
 647 * The value 'N' can be used as a dynamically substituted token for the
 648 * maximum allowed value; i.e (nmaskbits - 1).  Keep in mind that it is
 649 * dynamic, so if system changes cause the bitmap width to change, such
 650 * as more cores in a CPU list, then any ranges using N will also change.
 651 *
 652 * Returns: 0 on success, -errno on invalid input strings. Error values:
 653 *
 654 *   - ``-EINVAL``: wrong region format
 655 *   - ``-EINVAL``: invalid character in string
 656 *   - ``-ERANGE``: bit number specified too large for mask
 657 *   - ``-EOVERFLOW``: integer overflow in the input parameters
 658 */
 659int bitmap_parselist(const char *buf, unsigned long *maskp, int nmaskbits)
 660{
 661	struct region r;
 662	long ret;
 663
 664	r.nbits = nmaskbits;
 665	bitmap_zero(maskp, r.nbits);
 666
 667	while (buf) {
 668		buf = bitmap_find_region(buf);
 669		if (buf == NULL)
 670			return 0;
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 671
 672		buf = bitmap_parse_region(buf, &r);
 673		if (IS_ERR(buf))
 674			return PTR_ERR(buf);
 675
 676		ret = bitmap_check_region(&r);
 677		if (ret)
 678			return ret;
 679
 680		bitmap_set_region(&r, maskp);
 681	}
 
 
 682
 683	return 0;
 684}
 685EXPORT_SYMBOL(bitmap_parselist);
 686
 687
 688/**
 689 * bitmap_parselist_user()
 690 *
 691 * @ubuf: pointer to user buffer containing string.
 692 * @ulen: buffer size in bytes.  If string is smaller than this
 693 *    then it must be terminated with a \0.
 694 * @maskp: pointer to bitmap array that will contain result.
 695 * @nmaskbits: size of bitmap, in bits.
 696 *
 697 * Wrapper for bitmap_parselist(), providing it with user buffer.
 
 
 
 
 698 */
 699int bitmap_parselist_user(const char __user *ubuf,
 700			unsigned int ulen, unsigned long *maskp,
 701			int nmaskbits)
 702{
 703	char *buf;
 704	int ret;
 705
 706	buf = memdup_user_nul(ubuf, ulen);
 707	if (IS_ERR(buf))
 708		return PTR_ERR(buf);
 709
 710	ret = bitmap_parselist(buf, maskp, nmaskbits);
 711
 712	kfree(buf);
 713	return ret;
 714}
 715EXPORT_SYMBOL(bitmap_parselist_user);
 716
 717static const char *bitmap_get_x32_reverse(const char *start,
 718					const char *end, u32 *num)
 719{
 720	u32 ret = 0;
 721	int c, i;
 722
 723	for (i = 0; i < 32; i += 4) {
 724		c = hex_to_bin(*end--);
 725		if (c < 0)
 726			return ERR_PTR(-EINVAL);
 727
 728		ret |= c << i;
 729
 730		if (start > end || __end_of_region(*end))
 731			goto out;
 732	}
 733
 734	if (hex_to_bin(*end--) >= 0)
 735		return ERR_PTR(-EOVERFLOW);
 736out:
 737	*num = ret;
 738	return end;
 739}
 740
 741/**
 742 * bitmap_parse - convert an ASCII hex string into a bitmap.
 743 * @start: pointer to buffer containing string.
 744 * @buflen: buffer size in bytes.  If string is smaller than this
 745 *    then it must be terminated with a \0 or \n. In that case,
 746 *    UINT_MAX may be provided instead of string length.
 747 * @maskp: pointer to bitmap array that will contain result.
 748 * @nmaskbits: size of bitmap, in bits.
 749 *
 750 * Commas group hex digits into chunks.  Each chunk defines exactly 32
 751 * bits of the resultant bitmask.  No chunk may specify a value larger
 752 * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
 753 * then leading 0-bits are prepended.  %-EINVAL is returned for illegal
 754 * characters. Grouping such as "1,,5", ",44", "," or "" is allowed.
 755 * Leading, embedded and trailing whitespace accepted.
 756 */
 757int bitmap_parse(const char *start, unsigned int buflen,
 758		unsigned long *maskp, int nmaskbits)
 759{
 760	const char *end = strnchrnul(start, buflen, '\n') - 1;
 761	int chunks = BITS_TO_U32(nmaskbits);
 762	u32 *bitmap = (u32 *)maskp;
 763	int unset_bit;
 764	int chunk;
 765
 766	for (chunk = 0; ; chunk++) {
 767		end = bitmap_find_region_reverse(start, end);
 768		if (start > end)
 769			break;
 770
 771		if (!chunks--)
 772			return -EOVERFLOW;
 773
 774#if defined(CONFIG_64BIT) && defined(__BIG_ENDIAN)
 775		end = bitmap_get_x32_reverse(start, end, &bitmap[chunk ^ 1]);
 776#else
 777		end = bitmap_get_x32_reverse(start, end, &bitmap[chunk]);
 778#endif
 779		if (IS_ERR(end))
 780			return PTR_ERR(end);
 781	}
 782
 783	unset_bit = (BITS_TO_U32(nmaskbits) - chunks) * 32;
 784	if (unset_bit < nmaskbits) {
 785		bitmap_clear(maskp, unset_bit, nmaskbits - unset_bit);
 786		return 0;
 787	}
 788
 789	if (find_next_bit(maskp, unset_bit, nmaskbits) != unset_bit)
 790		return -EOVERFLOW;
 791
 792	return 0;
 793}
 794EXPORT_SYMBOL(bitmap_parse);
 795
 796/**
 797 * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
 798 *	@buf: pointer to a bitmap
 799 *	@pos: a bit position in @buf (0 <= @pos < @nbits)
 800 *	@nbits: number of valid bit positions in @buf
 801 *
 802 * Map the bit at position @pos in @buf (of length @nbits) to the
 803 * ordinal of which set bit it is.  If it is not set or if @pos
 804 * is not a valid bit position, map to -1.
 805 *
 806 * If for example, just bits 4 through 7 are set in @buf, then @pos
 807 * values 4 through 7 will get mapped to 0 through 3, respectively,
 808 * and other @pos values will get mapped to -1.  When @pos value 7
 809 * gets mapped to (returns) @ord value 3 in this example, that means
 810 * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
 811 *
 812 * The bit positions 0 through @bits are valid positions in @buf.
 813 */
 814static int bitmap_pos_to_ord(const unsigned long *buf, unsigned int pos, unsigned int nbits)
 815{
 816	if (pos >= nbits || !test_bit(pos, buf))
 
 
 817		return -1;
 818
 819	return __bitmap_weight(buf, pos);
 
 
 
 
 
 
 
 
 820}
 821
 822/**
 823 * bitmap_ord_to_pos - find position of n-th set bit in bitmap
 824 *	@buf: pointer to bitmap
 825 *	@ord: ordinal bit position (n-th set bit, n >= 0)
 826 *	@nbits: number of valid bit positions in @buf
 827 *
 828 * Map the ordinal offset of bit @ord in @buf to its position in @buf.
 829 * Value of @ord should be in range 0 <= @ord < weight(buf). If @ord
 830 * >= weight(buf), returns @nbits.
 831 *
 832 * If for example, just bits 4 through 7 are set in @buf, then @ord
 833 * values 0 through 3 will get mapped to 4 through 7, respectively,
 834 * and all other @ord values returns @nbits.  When @ord value 3
 835 * gets mapped to (returns) @pos value 7 in this example, that means
 836 * that the 3rd set bit (starting with 0th) is at position 7 in @buf.
 837 *
 838 * The bit positions 0 through @nbits-1 are valid positions in @buf.
 839 */
 840unsigned int bitmap_ord_to_pos(const unsigned long *buf, unsigned int ord, unsigned int nbits)
 841{
 842	unsigned int pos;
 
 
 
 843
 844	for (pos = find_first_bit(buf, nbits);
 845	     pos < nbits && ord;
 846	     pos = find_next_bit(buf, nbits, pos + 1))
 847		ord--;
 
 
 
 848
 849	return pos;
 850}
 851
 852/**
 853 * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
 854 *	@dst: remapped result
 855 *	@src: subset to be remapped
 856 *	@old: defines domain of map
 857 *	@new: defines range of map
 858 *	@nbits: number of bits in each of these bitmaps
 859 *
 860 * Let @old and @new define a mapping of bit positions, such that
 861 * whatever position is held by the n-th set bit in @old is mapped
 862 * to the n-th set bit in @new.  In the more general case, allowing
 863 * for the possibility that the weight 'w' of @new is less than the
 864 * weight of @old, map the position of the n-th set bit in @old to
 865 * the position of the m-th set bit in @new, where m == n % w.
 866 *
 867 * If either of the @old and @new bitmaps are empty, or if @src and
 868 * @dst point to the same location, then this routine copies @src
 869 * to @dst.
 870 *
 871 * The positions of unset bits in @old are mapped to themselves
 872 * (the identify map).
 873 *
 874 * Apply the above specified mapping to @src, placing the result in
 875 * @dst, clearing any bits previously set in @dst.
 876 *
 877 * For example, lets say that @old has bits 4 through 7 set, and
 878 * @new has bits 12 through 15 set.  This defines the mapping of bit
 879 * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
 880 * bit positions unchanged.  So if say @src comes into this routine
 881 * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
 882 * 13 and 15 set.
 883 */
 884void bitmap_remap(unsigned long *dst, const unsigned long *src,
 885		const unsigned long *old, const unsigned long *new,
 886		unsigned int nbits)
 887{
 888	unsigned int oldbit, w;
 889
 890	if (dst == src)		/* following doesn't handle inplace remaps */
 891		return;
 892	bitmap_zero(dst, nbits);
 893
 894	w = bitmap_weight(new, nbits);
 895	for_each_set_bit(oldbit, src, nbits) {
 896		int n = bitmap_pos_to_ord(old, oldbit, nbits);
 897
 898		if (n < 0 || w == 0)
 899			set_bit(oldbit, dst);	/* identity map */
 900		else
 901			set_bit(bitmap_ord_to_pos(new, n % w, nbits), dst);
 902	}
 903}
 904EXPORT_SYMBOL(bitmap_remap);
 905
 906/**
 907 * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
 908 *	@oldbit: bit position to be mapped
 909 *	@old: defines domain of map
 910 *	@new: defines range of map
 911 *	@bits: number of bits in each of these bitmaps
 912 *
 913 * Let @old and @new define a mapping of bit positions, such that
 914 * whatever position is held by the n-th set bit in @old is mapped
 915 * to the n-th set bit in @new.  In the more general case, allowing
 916 * for the possibility that the weight 'w' of @new is less than the
 917 * weight of @old, map the position of the n-th set bit in @old to
 918 * the position of the m-th set bit in @new, where m == n % w.
 919 *
 920 * The positions of unset bits in @old are mapped to themselves
 921 * (the identify map).
 922 *
 923 * Apply the above specified mapping to bit position @oldbit, returning
 924 * the new bit position.
 925 *
 926 * For example, lets say that @old has bits 4 through 7 set, and
 927 * @new has bits 12 through 15 set.  This defines the mapping of bit
 928 * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
 929 * bit positions unchanged.  So if say @oldbit is 5, then this routine
 930 * returns 13.
 931 */
 932int bitmap_bitremap(int oldbit, const unsigned long *old,
 933				const unsigned long *new, int bits)
 934{
 935	int w = bitmap_weight(new, bits);
 936	int n = bitmap_pos_to_ord(old, oldbit, bits);
 937	if (n < 0 || w == 0)
 938		return oldbit;
 939	else
 940		return bitmap_ord_to_pos(new, n % w, bits);
 941}
 942EXPORT_SYMBOL(bitmap_bitremap);
 943
 944#ifdef CONFIG_NUMA
 945/**
 946 * bitmap_onto - translate one bitmap relative to another
 947 *	@dst: resulting translated bitmap
 948 * 	@orig: original untranslated bitmap
 949 * 	@relmap: bitmap relative to which translated
 950 *	@bits: number of bits in each of these bitmaps
 951 *
 952 * Set the n-th bit of @dst iff there exists some m such that the
 953 * n-th bit of @relmap is set, the m-th bit of @orig is set, and
 954 * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
 955 * (If you understood the previous sentence the first time your
 956 * read it, you're overqualified for your current job.)
 957 *
 958 * In other words, @orig is mapped onto (surjectively) @dst,
 959 * using the map { <n, m> | the n-th bit of @relmap is the
 960 * m-th set bit of @relmap }.
 961 *
 962 * Any set bits in @orig above bit number W, where W is the
 963 * weight of (number of set bits in) @relmap are mapped nowhere.
 964 * In particular, if for all bits m set in @orig, m >= W, then
 965 * @dst will end up empty.  In situations where the possibility
 966 * of such an empty result is not desired, one way to avoid it is
 967 * to use the bitmap_fold() operator, below, to first fold the
 968 * @orig bitmap over itself so that all its set bits x are in the
 969 * range 0 <= x < W.  The bitmap_fold() operator does this by
 970 * setting the bit (m % W) in @dst, for each bit (m) set in @orig.
 971 *
 972 * Example [1] for bitmap_onto():
 973 *  Let's say @relmap has bits 30-39 set, and @orig has bits
 974 *  1, 3, 5, 7, 9 and 11 set.  Then on return from this routine,
 975 *  @dst will have bits 31, 33, 35, 37 and 39 set.
 976 *
 977 *  When bit 0 is set in @orig, it means turn on the bit in
 978 *  @dst corresponding to whatever is the first bit (if any)
 979 *  that is turned on in @relmap.  Since bit 0 was off in the
 980 *  above example, we leave off that bit (bit 30) in @dst.
 981 *
 982 *  When bit 1 is set in @orig (as in the above example), it
 983 *  means turn on the bit in @dst corresponding to whatever
 984 *  is the second bit that is turned on in @relmap.  The second
 985 *  bit in @relmap that was turned on in the above example was
 986 *  bit 31, so we turned on bit 31 in @dst.
 987 *
 988 *  Similarly, we turned on bits 33, 35, 37 and 39 in @dst,
 989 *  because they were the 4th, 6th, 8th and 10th set bits
 990 *  set in @relmap, and the 4th, 6th, 8th and 10th bits of
 991 *  @orig (i.e. bits 3, 5, 7 and 9) were also set.
 992 *
 993 *  When bit 11 is set in @orig, it means turn on the bit in
 994 *  @dst corresponding to whatever is the twelfth bit that is
 995 *  turned on in @relmap.  In the above example, there were
 996 *  only ten bits turned on in @relmap (30..39), so that bit
 997 *  11 was set in @orig had no affect on @dst.
 998 *
 999 * Example [2] for bitmap_fold() + bitmap_onto():
1000 *  Let's say @relmap has these ten bits set::
1001 *
1002 *		40 41 42 43 45 48 53 61 74 95
1003 *
1004 *  (for the curious, that's 40 plus the first ten terms of the
1005 *  Fibonacci sequence.)
1006 *
1007 *  Further lets say we use the following code, invoking
1008 *  bitmap_fold() then bitmap_onto, as suggested above to
1009 *  avoid the possibility of an empty @dst result::
1010 *
1011 *	unsigned long *tmp;	// a temporary bitmap's bits
1012 *
1013 *	bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
1014 *	bitmap_onto(dst, tmp, relmap, bits);
1015 *
1016 *  Then this table shows what various values of @dst would be, for
1017 *  various @orig's.  I list the zero-based positions of each set bit.
1018 *  The tmp column shows the intermediate result, as computed by
1019 *  using bitmap_fold() to fold the @orig bitmap modulo ten
1020 *  (the weight of @relmap):
1021 *
1022 *      =============== ============== =================
1023 *      @orig           tmp            @dst
1024 *      0                0             40
1025 *      1                1             41
1026 *      9                9             95
1027 *      10               0             40 [#f1]_
1028 *      1 3 5 7          1 3 5 7       41 43 48 61
1029 *      0 1 2 3 4        0 1 2 3 4     40 41 42 43 45
1030 *      0 9 18 27        0 9 8 7       40 61 74 95
1031 *      0 10 20 30       0             40
1032 *      0 11 22 33       0 1 2 3       40 41 42 43
1033 *      0 12 24 36       0 2 4 6       40 42 45 53
1034 *      78 102 211       1 2 8         41 42 74 [#f1]_
1035 *      =============== ============== =================
1036 *
1037 * .. [#f1]
1038 *
1039 *     For these marked lines, if we hadn't first done bitmap_fold()
1040 *     into tmp, then the @dst result would have been empty.
1041 *
1042 * If either of @orig or @relmap is empty (no set bits), then @dst
1043 * will be returned empty.
1044 *
1045 * If (as explained above) the only set bits in @orig are in positions
1046 * m where m >= W, (where W is the weight of @relmap) then @dst will
1047 * once again be returned empty.
1048 *
1049 * All bits in @dst not set by the above rule are cleared.
1050 */
1051void bitmap_onto(unsigned long *dst, const unsigned long *orig,
1052			const unsigned long *relmap, unsigned int bits)
1053{
1054	unsigned int n, m;	/* same meaning as in above comment */
1055
1056	if (dst == orig)	/* following doesn't handle inplace mappings */
1057		return;
1058	bitmap_zero(dst, bits);
1059
1060	/*
1061	 * The following code is a more efficient, but less
1062	 * obvious, equivalent to the loop:
1063	 *	for (m = 0; m < bitmap_weight(relmap, bits); m++) {
1064	 *		n = bitmap_ord_to_pos(orig, m, bits);
1065	 *		if (test_bit(m, orig))
1066	 *			set_bit(n, dst);
1067	 *	}
1068	 */
1069
1070	m = 0;
1071	for_each_set_bit(n, relmap, bits) {
1072		/* m == bitmap_pos_to_ord(relmap, n, bits) */
1073		if (test_bit(m, orig))
1074			set_bit(n, dst);
1075		m++;
1076	}
1077}
 
1078
1079/**
1080 * bitmap_fold - fold larger bitmap into smaller, modulo specified size
1081 *	@dst: resulting smaller bitmap
1082 *	@orig: original larger bitmap
1083 *	@sz: specified size
1084 *	@nbits: number of bits in each of these bitmaps
1085 *
1086 * For each bit oldbit in @orig, set bit oldbit mod @sz in @dst.
1087 * Clear all other bits in @dst.  See further the comment and
1088 * Example [2] for bitmap_onto() for why and how to use this.
1089 */
1090void bitmap_fold(unsigned long *dst, const unsigned long *orig,
1091			unsigned int sz, unsigned int nbits)
1092{
1093	unsigned int oldbit;
1094
1095	if (dst == orig)	/* following doesn't handle inplace mappings */
1096		return;
1097	bitmap_zero(dst, nbits);
1098
1099	for_each_set_bit(oldbit, orig, nbits)
1100		set_bit(oldbit % sz, dst);
1101}
1102#endif /* CONFIG_NUMA */
1103
1104/*
1105 * Common code for bitmap_*_region() routines.
1106 *	bitmap: array of unsigned longs corresponding to the bitmap
1107 *	pos: the beginning of the region
1108 *	order: region size (log base 2 of number of bits)
1109 *	reg_op: operation(s) to perform on that region of bitmap
1110 *
1111 * Can set, verify and/or release a region of bits in a bitmap,
1112 * depending on which combination of REG_OP_* flag bits is set.
1113 *
1114 * A region of a bitmap is a sequence of bits in the bitmap, of
1115 * some size '1 << order' (a power of two), aligned to that same
1116 * '1 << order' power of two.
1117 *
1118 * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
1119 * Returns 0 in all other cases and reg_ops.
1120 */
1121
1122enum {
1123	REG_OP_ISFREE,		/* true if region is all zero bits */
1124	REG_OP_ALLOC,		/* set all bits in region */
1125	REG_OP_RELEASE,		/* clear all bits in region */
1126};
1127
1128static int __reg_op(unsigned long *bitmap, unsigned int pos, int order, int reg_op)
1129{
1130	int nbits_reg;		/* number of bits in region */
1131	int index;		/* index first long of region in bitmap */
1132	int offset;		/* bit offset region in bitmap[index] */
1133	int nlongs_reg;		/* num longs spanned by region in bitmap */
1134	int nbitsinlong;	/* num bits of region in each spanned long */
1135	unsigned long mask;	/* bitmask for one long of region */
1136	int i;			/* scans bitmap by longs */
1137	int ret = 0;		/* return value */
1138
1139	/*
1140	 * Either nlongs_reg == 1 (for small orders that fit in one long)
1141	 * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
1142	 */
1143	nbits_reg = 1 << order;
1144	index = pos / BITS_PER_LONG;
1145	offset = pos - (index * BITS_PER_LONG);
1146	nlongs_reg = BITS_TO_LONGS(nbits_reg);
1147	nbitsinlong = min(nbits_reg,  BITS_PER_LONG);
1148
1149	/*
1150	 * Can't do "mask = (1UL << nbitsinlong) - 1", as that
1151	 * overflows if nbitsinlong == BITS_PER_LONG.
1152	 */
1153	mask = (1UL << (nbitsinlong - 1));
1154	mask += mask - 1;
1155	mask <<= offset;
1156
1157	switch (reg_op) {
1158	case REG_OP_ISFREE:
1159		for (i = 0; i < nlongs_reg; i++) {
1160			if (bitmap[index + i] & mask)
1161				goto done;
1162		}
1163		ret = 1;	/* all bits in region free (zero) */
1164		break;
1165
1166	case REG_OP_ALLOC:
1167		for (i = 0; i < nlongs_reg; i++)
1168			bitmap[index + i] |= mask;
1169		break;
1170
1171	case REG_OP_RELEASE:
1172		for (i = 0; i < nlongs_reg; i++)
1173			bitmap[index + i] &= ~mask;
1174		break;
1175	}
1176done:
1177	return ret;
1178}
1179
1180/**
1181 * bitmap_find_free_region - find a contiguous aligned mem region
1182 *	@bitmap: array of unsigned longs corresponding to the bitmap
1183 *	@bits: number of bits in the bitmap
1184 *	@order: region size (log base 2 of number of bits) to find
1185 *
1186 * Find a region of free (zero) bits in a @bitmap of @bits bits and
1187 * allocate them (set them to one).  Only consider regions of length
1188 * a power (@order) of two, aligned to that power of two, which
1189 * makes the search algorithm much faster.
1190 *
1191 * Return the bit offset in bitmap of the allocated region,
1192 * or -errno on failure.
1193 */
1194int bitmap_find_free_region(unsigned long *bitmap, unsigned int bits, int order)
1195{
1196	unsigned int pos, end;		/* scans bitmap by regions of size order */
1197
1198	for (pos = 0 ; (end = pos + (1U << order)) <= bits; pos = end) {
1199		if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1200			continue;
1201		__reg_op(bitmap, pos, order, REG_OP_ALLOC);
1202		return pos;
1203	}
1204	return -ENOMEM;
1205}
1206EXPORT_SYMBOL(bitmap_find_free_region);
1207
1208/**
1209 * bitmap_release_region - release allocated bitmap region
1210 *	@bitmap: array of unsigned longs corresponding to the bitmap
1211 *	@pos: beginning of bit region to release
1212 *	@order: region size (log base 2 of number of bits) to release
1213 *
1214 * This is the complement to __bitmap_find_free_region() and releases
1215 * the found region (by clearing it in the bitmap).
1216 *
1217 * No return value.
1218 */
1219void bitmap_release_region(unsigned long *bitmap, unsigned int pos, int order)
1220{
1221	__reg_op(bitmap, pos, order, REG_OP_RELEASE);
1222}
1223EXPORT_SYMBOL(bitmap_release_region);
1224
1225/**
1226 * bitmap_allocate_region - allocate bitmap region
1227 *	@bitmap: array of unsigned longs corresponding to the bitmap
1228 *	@pos: beginning of bit region to allocate
1229 *	@order: region size (log base 2 of number of bits) to allocate
1230 *
1231 * Allocate (set bits in) a specified region of a bitmap.
1232 *
1233 * Return 0 on success, or %-EBUSY if specified region wasn't
1234 * free (not all bits were zero).
1235 */
1236int bitmap_allocate_region(unsigned long *bitmap, unsigned int pos, int order)
1237{
1238	if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
1239		return -EBUSY;
1240	return __reg_op(bitmap, pos, order, REG_OP_ALLOC);
 
1241}
1242EXPORT_SYMBOL(bitmap_allocate_region);
1243
1244/**
1245 * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
1246 * @dst:   destination buffer
1247 * @src:   bitmap to copy
1248 * @nbits: number of bits in the bitmap
1249 *
1250 * Require nbits % BITS_PER_LONG == 0.
1251 */
1252#ifdef __BIG_ENDIAN
1253void bitmap_copy_le(unsigned long *dst, const unsigned long *src, unsigned int nbits)
1254{
1255	unsigned int i;
 
1256
1257	for (i = 0; i < nbits/BITS_PER_LONG; i++) {
1258		if (BITS_PER_LONG == 64)
1259			dst[i] = cpu_to_le64(src[i]);
1260		else
1261			dst[i] = cpu_to_le32(src[i]);
1262	}
1263}
1264EXPORT_SYMBOL(bitmap_copy_le);
1265#endif
1266
1267unsigned long *bitmap_alloc(unsigned int nbits, gfp_t flags)
1268{
1269	return kmalloc_array(BITS_TO_LONGS(nbits), sizeof(unsigned long),
1270			     flags);
1271}
1272EXPORT_SYMBOL(bitmap_alloc);
1273
1274unsigned long *bitmap_zalloc(unsigned int nbits, gfp_t flags)
1275{
1276	return bitmap_alloc(nbits, flags | __GFP_ZERO);
1277}
1278EXPORT_SYMBOL(bitmap_zalloc);
1279
1280void bitmap_free(const unsigned long *bitmap)
1281{
1282	kfree(bitmap);
1283}
1284EXPORT_SYMBOL(bitmap_free);
1285
1286static void devm_bitmap_free(void *data)
1287{
1288	unsigned long *bitmap = data;
1289
1290	bitmap_free(bitmap);
1291}
1292
1293unsigned long *devm_bitmap_alloc(struct device *dev,
1294				 unsigned int nbits, gfp_t flags)
1295{
1296	unsigned long *bitmap;
1297	int ret;
1298
1299	bitmap = bitmap_alloc(nbits, flags);
1300	if (!bitmap)
1301		return NULL;
1302
1303	ret = devm_add_action_or_reset(dev, devm_bitmap_free, bitmap);
1304	if (ret)
1305		return NULL;
1306
1307	return bitmap;
1308}
1309EXPORT_SYMBOL_GPL(devm_bitmap_alloc);
1310
1311unsigned long *devm_bitmap_zalloc(struct device *dev,
1312				  unsigned int nbits, gfp_t flags)
1313{
1314	return devm_bitmap_alloc(dev, nbits, flags | __GFP_ZERO);
1315}
1316EXPORT_SYMBOL_GPL(devm_bitmap_zalloc);
1317
1318#if BITS_PER_LONG == 64
1319/**
1320 * bitmap_from_arr32 - copy the contents of u32 array of bits to bitmap
1321 *	@bitmap: array of unsigned longs, the destination bitmap
1322 *	@buf: array of u32 (in host byte order), the source bitmap
1323 *	@nbits: number of bits in @bitmap
1324 */
1325void bitmap_from_arr32(unsigned long *bitmap, const u32 *buf, unsigned int nbits)
1326{
1327	unsigned int i, halfwords;
1328
1329	halfwords = DIV_ROUND_UP(nbits, 32);
1330	for (i = 0; i < halfwords; i++) {
1331		bitmap[i/2] = (unsigned long) buf[i];
1332		if (++i < halfwords)
1333			bitmap[i/2] |= ((unsigned long) buf[i]) << 32;
1334	}
1335
1336	/* Clear tail bits in last word beyond nbits. */
1337	if (nbits % BITS_PER_LONG)
1338		bitmap[(halfwords - 1) / 2] &= BITMAP_LAST_WORD_MASK(nbits);
1339}
1340EXPORT_SYMBOL(bitmap_from_arr32);
1341
1342/**
1343 * bitmap_to_arr32 - copy the contents of bitmap to a u32 array of bits
1344 *	@buf: array of u32 (in host byte order), the dest bitmap
1345 *	@bitmap: array of unsigned longs, the source bitmap
1346 *	@nbits: number of bits in @bitmap
1347 */
1348void bitmap_to_arr32(u32 *buf, const unsigned long *bitmap, unsigned int nbits)
1349{
1350	unsigned int i, halfwords;
1351
1352	halfwords = DIV_ROUND_UP(nbits, 32);
1353	for (i = 0; i < halfwords; i++) {
1354		buf[i] = (u32) (bitmap[i/2] & UINT_MAX);
1355		if (++i < halfwords)
1356			buf[i] = (u32) (bitmap[i/2] >> 32);
1357	}
1358
1359	/* Clear tail bits in last element of array beyond nbits. */
1360	if (nbits % BITS_PER_LONG)
1361		buf[halfwords - 1] &= (u32) (UINT_MAX >> ((-nbits) & 31));
1362}
1363EXPORT_SYMBOL(bitmap_to_arr32);
1364
1365#endif