debuggers.hg

annotate xen/common/bitmap.c @ 22855:1d1eec7e1fb4

xl: Perform minimal validation of virtual disk file while parsing config file

This patch performs some very basic validation on the virtual disk
file passed through the config file. This validation ensures that we
don't go too far with the initialization like spawn qemu and more
while there could be some potentially fundamental issues.

[ Patch fixed up to work with PHYSTYPE_EMPTY 22808:6ec61438713a -iwj ]

Signed-off-by: Kamala Narasimhan <kamala.narasimhan@citrix.com>
Acked-by: Ian Jackson <ian.jackson@eu.citrix.com>
Signed-off-by: Ian Jackson <ian.jackson@eu.citrix.com>
Committed-by: Ian Jackson <ian.jackson@eu.citrix.com>
author Kamala Narasimhan <kamala.narasimhan@gmail.com>
date Tue Jan 25 18:09:49 2011 +0000 (2011-01-25)
parents 7c455af5998a
children
rev   line source
kaf24@4842 1 /*
kaf24@4842 2 * lib/bitmap.c
kaf24@4842 3 * Helper functions for bitmap.h.
kaf24@4842 4 *
kaf24@4842 5 * This source code is licensed under the GNU General Public License,
kaf24@4842 6 * Version 2. See the file COPYING for more details.
kaf24@4842 7 */
kaf24@4842 8 #include <xen/config.h>
kaf24@4842 9 #include <xen/types.h>
kaf24@4842 10 #include <xen/errno.h>
kaf24@4842 11 #include <xen/bitmap.h>
kaf24@4842 12 #include <xen/bitops.h>
kfraser@13540 13 #include <asm/byteorder.h>
kaf24@4842 14
kaf24@4842 15 /*
kaf24@4842 16 * bitmaps provide an array of bits, implemented using an an
kaf24@4842 17 * array of unsigned longs. The number of valid bits in a
kaf24@4842 18 * given bitmap does _not_ need to be an exact multiple of
kaf24@4842 19 * BITS_PER_LONG.
kaf24@4842 20 *
kaf24@4842 21 * The possible unused bits in the last, partially used word
kaf24@4842 22 * of a bitmap are 'don't care'. The implementation makes
kaf24@4842 23 * no particular effort to keep them zero. It ensures that
kaf24@4842 24 * their value will not affect the results of any operation.
kaf24@4842 25 * The bitmap operations that return Boolean (bitmap_empty,
kaf24@4842 26 * for example) or scalar (bitmap_weight, for example) results
kaf24@4842 27 * carefully filter out these unused bits from impacting their
kaf24@4842 28 * results.
kaf24@4842 29 *
kaf24@4842 30 * These operations actually hold to a slightly stronger rule:
kaf24@4842 31 * if you don't input any bitmaps to these ops that have some
kaf24@4842 32 * unused bits set, then they won't output any set unused bits
kaf24@4842 33 * in output bitmaps.
kaf24@4842 34 *
kaf24@4842 35 * The byte ordering of bitmaps is more natural on little
kaf24@4842 36 * endian architectures. See the big-endian headers
kaf24@4842 37 * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
kaf24@4842 38 * for the best explanations of this ordering.
kaf24@4842 39 */
kaf24@4842 40
kaf24@4842 41 int __bitmap_empty(const unsigned long *bitmap, int bits)
kaf24@4842 42 {
kaf24@4842 43 int k, lim = bits/BITS_PER_LONG;
kaf24@4842 44 for (k = 0; k < lim; ++k)
kaf24@4842 45 if (bitmap[k])
kaf24@4842 46 return 0;
kaf24@4842 47
kaf24@4842 48 if (bits % BITS_PER_LONG)
kaf24@4842 49 if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
kaf24@4842 50 return 0;
kaf24@4842 51
kaf24@4842 52 return 1;
kaf24@4842 53 }
kaf24@4842 54 EXPORT_SYMBOL(__bitmap_empty);
kaf24@4842 55
kaf24@4842 56 int __bitmap_full(const unsigned long *bitmap, int bits)
kaf24@4842 57 {
kaf24@4842 58 int k, lim = bits/BITS_PER_LONG;
kaf24@4842 59 for (k = 0; k < lim; ++k)
kaf24@4842 60 if (~bitmap[k])
kaf24@4842 61 return 0;
kaf24@4842 62
kaf24@4842 63 if (bits % BITS_PER_LONG)
kaf24@4842 64 if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
kaf24@4842 65 return 0;
kaf24@4842 66
kaf24@4842 67 return 1;
kaf24@4842 68 }
kaf24@4842 69 EXPORT_SYMBOL(__bitmap_full);
kaf24@4842 70
kaf24@4842 71 int __bitmap_equal(const unsigned long *bitmap1,
kaf24@4842 72 const unsigned long *bitmap2, int bits)
kaf24@4842 73 {
kaf24@4842 74 int k, lim = bits/BITS_PER_LONG;
kaf24@4842 75 for (k = 0; k < lim; ++k)
kaf24@4842 76 if (bitmap1[k] != bitmap2[k])
kaf24@4842 77 return 0;
kaf24@4842 78
kaf24@4842 79 if (bits % BITS_PER_LONG)
kaf24@4842 80 if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
kaf24@4842 81 return 0;
kaf24@4842 82
kaf24@4842 83 return 1;
kaf24@4842 84 }
kaf24@4842 85 EXPORT_SYMBOL(__bitmap_equal);
kaf24@4842 86
kaf24@4842 87 void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits)
kaf24@4842 88 {
kaf24@4842 89 int k, lim = bits/BITS_PER_LONG;
kaf24@4842 90 for (k = 0; k < lim; ++k)
kaf24@4842 91 dst[k] = ~src[k];
kaf24@4842 92
kaf24@4842 93 if (bits % BITS_PER_LONG)
kaf24@4842 94 dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);
kaf24@4842 95 }
kaf24@4842 96 EXPORT_SYMBOL(__bitmap_complement);
kaf24@4842 97
kaf24@4842 98 /*
kaf24@4842 99 * __bitmap_shift_right - logical right shift of the bits in a bitmap
kaf24@4842 100 * @dst - destination bitmap
kaf24@4842 101 * @src - source bitmap
kaf24@4842 102 * @nbits - shift by this many bits
kaf24@4842 103 * @bits - bitmap size, in bits
kaf24@4842 104 *
kaf24@4842 105 * Shifting right (dividing) means moving bits in the MS -> LS bit
kaf24@4842 106 * direction. Zeros are fed into the vacated MS positions and the
kaf24@4842 107 * LS bits shifted off the bottom are lost.
kaf24@4842 108 */
kaf24@4842 109 void __bitmap_shift_right(unsigned long *dst,
kaf24@4842 110 const unsigned long *src, int shift, int bits)
kaf24@4842 111 {
kaf24@4842 112 int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
kaf24@4842 113 int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
kaf24@4842 114 unsigned long mask = (1UL << left) - 1;
kaf24@4842 115 for (k = 0; off + k < lim; ++k) {
kaf24@4842 116 unsigned long upper, lower;
kaf24@4842 117
kaf24@4842 118 /*
kaf24@4842 119 * If shift is not word aligned, take lower rem bits of
kaf24@4842 120 * word above and make them the top rem bits of result.
kaf24@4842 121 */
kaf24@4842 122 if (!rem || off + k + 1 >= lim)
kaf24@4842 123 upper = 0;
kaf24@4842 124 else {
kaf24@4842 125 upper = src[off + k + 1];
kaf24@4842 126 if (off + k + 1 == lim - 1 && left)
kaf24@4842 127 upper &= mask;
kaf24@4842 128 }
kaf24@4842 129 lower = src[off + k];
kaf24@4842 130 if (left && off + k == lim - 1)
kaf24@4842 131 lower &= mask;
kaf24@4842 132 dst[k] = upper << (BITS_PER_LONG - rem) | lower >> rem;
kaf24@4842 133 if (left && k == lim - 1)
kaf24@4842 134 dst[k] &= mask;
kaf24@4842 135 }
kaf24@4842 136 if (off)
kaf24@4842 137 memset(&dst[lim - off], 0, off*sizeof(unsigned long));
kaf24@4842 138 }
kaf24@4842 139 EXPORT_SYMBOL(__bitmap_shift_right);
kaf24@4842 140
kaf24@4842 141
kaf24@4842 142 /*
kaf24@4842 143 * __bitmap_shift_left - logical left shift of the bits in a bitmap
kaf24@4842 144 * @dst - destination bitmap
kaf24@4842 145 * @src - source bitmap
kaf24@4842 146 * @nbits - shift by this many bits
kaf24@4842 147 * @bits - bitmap size, in bits
kaf24@4842 148 *
kaf24@4842 149 * Shifting left (multiplying) means moving bits in the LS -> MS
kaf24@4842 150 * direction. Zeros are fed into the vacated LS bit positions
kaf24@4842 151 * and those MS bits shifted off the top are lost.
kaf24@4842 152 */
kaf24@4842 153
kaf24@4842 154 void __bitmap_shift_left(unsigned long *dst,
kaf24@4842 155 const unsigned long *src, int shift, int bits)
kaf24@4842 156 {
kaf24@4842 157 int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
kaf24@4842 158 int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
kaf24@4842 159 for (k = lim - off - 1; k >= 0; --k) {
kaf24@4842 160 unsigned long upper, lower;
kaf24@4842 161
kaf24@4842 162 /*
kaf24@4842 163 * If shift is not word aligned, take upper rem bits of
kaf24@4842 164 * word below and make them the bottom rem bits of result.
kaf24@4842 165 */
kaf24@4842 166 if (rem && k > 0)
kaf24@4842 167 lower = src[k - 1];
kaf24@4842 168 else
kaf24@4842 169 lower = 0;
kaf24@4842 170 upper = src[k];
kaf24@4842 171 if (left && k == lim - 1)
kaf24@4842 172 upper &= (1UL << left) - 1;
kaf24@4842 173 dst[k + off] = lower >> (BITS_PER_LONG - rem) | upper << rem;
kaf24@4842 174 if (left && k + off == lim - 1)
kaf24@4842 175 dst[k + off] &= (1UL << left) - 1;
kaf24@4842 176 }
kaf24@4842 177 if (off)
kaf24@4842 178 memset(dst, 0, off*sizeof(unsigned long));
kaf24@4842 179 }
kaf24@4842 180 EXPORT_SYMBOL(__bitmap_shift_left);
kaf24@4842 181
kaf24@4842 182 void __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
kaf24@4842 183 const unsigned long *bitmap2, int bits)
kaf24@4842 184 {
kaf24@4842 185 int k;
kaf24@4842 186 int nr = BITS_TO_LONGS(bits);
kaf24@4842 187
kaf24@4842 188 for (k = 0; k < nr; k++)
kaf24@4842 189 dst[k] = bitmap1[k] & bitmap2[k];
kaf24@4842 190 }
kaf24@4842 191 EXPORT_SYMBOL(__bitmap_and);
kaf24@4842 192
kaf24@4842 193 void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
kaf24@4842 194 const unsigned long *bitmap2, int bits)
kaf24@4842 195 {
kaf24@4842 196 int k;
kaf24@4842 197 int nr = BITS_TO_LONGS(bits);
kaf24@4842 198
kaf24@4842 199 for (k = 0; k < nr; k++)
kaf24@4842 200 dst[k] = bitmap1[k] | bitmap2[k];
kaf24@4842 201 }
kaf24@4842 202 EXPORT_SYMBOL(__bitmap_or);
kaf24@4842 203
kaf24@4842 204 void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
kaf24@4842 205 const unsigned long *bitmap2, int bits)
kaf24@4842 206 {
kaf24@4842 207 int k;
kaf24@4842 208 int nr = BITS_TO_LONGS(bits);
kaf24@4842 209
kaf24@4842 210 for (k = 0; k < nr; k++)
kaf24@4842 211 dst[k] = bitmap1[k] ^ bitmap2[k];
kaf24@4842 212 }
kaf24@4842 213 EXPORT_SYMBOL(__bitmap_xor);
kaf24@4842 214
kaf24@4842 215 void __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
kaf24@4842 216 const unsigned long *bitmap2, int bits)
kaf24@4842 217 {
kaf24@4842 218 int k;
kaf24@4842 219 int nr = BITS_TO_LONGS(bits);
kaf24@4842 220
kaf24@4842 221 for (k = 0; k < nr; k++)
kaf24@4842 222 dst[k] = bitmap1[k] & ~bitmap2[k];
kaf24@4842 223 }
kaf24@4842 224 EXPORT_SYMBOL(__bitmap_andnot);
kaf24@4842 225
kaf24@4842 226 int __bitmap_intersects(const unsigned long *bitmap1,
kaf24@4842 227 const unsigned long *bitmap2, int bits)
kaf24@4842 228 {
kaf24@4842 229 int k, lim = bits/BITS_PER_LONG;
kaf24@4842 230 for (k = 0; k < lim; ++k)
kaf24@4842 231 if (bitmap1[k] & bitmap2[k])
kaf24@4842 232 return 1;
kaf24@4842 233
kaf24@4842 234 if (bits % BITS_PER_LONG)
kaf24@4842 235 if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
kaf24@4842 236 return 1;
kaf24@4842 237 return 0;
kaf24@4842 238 }
kaf24@4842 239 EXPORT_SYMBOL(__bitmap_intersects);
kaf24@4842 240
kaf24@4842 241 int __bitmap_subset(const unsigned long *bitmap1,
kaf24@4842 242 const unsigned long *bitmap2, int bits)
kaf24@4842 243 {
kaf24@4842 244 int k, lim = bits/BITS_PER_LONG;
kaf24@4842 245 for (k = 0; k < lim; ++k)
kaf24@4842 246 if (bitmap1[k] & ~bitmap2[k])
kaf24@4842 247 return 0;
kaf24@4842 248
kaf24@4842 249 if (bits % BITS_PER_LONG)
kaf24@4842 250 if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
kaf24@4842 251 return 0;
kaf24@4842 252 return 1;
kaf24@4842 253 }
kaf24@4842 254 EXPORT_SYMBOL(__bitmap_subset);
kaf24@4842 255
kaf24@4842 256 #if BITS_PER_LONG == 32
kaf24@4842 257 int __bitmap_weight(const unsigned long *bitmap, int bits)
kaf24@4842 258 {
kaf24@4842 259 int k, w = 0, lim = bits/BITS_PER_LONG;
kaf24@4842 260
kaf24@4842 261 for (k = 0; k < lim; k++)
kaf24@4842 262 w += hweight32(bitmap[k]);
kaf24@4842 263
kaf24@4842 264 if (bits % BITS_PER_LONG)
kaf24@4842 265 w += hweight32(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
kaf24@4842 266
kaf24@4842 267 return w;
kaf24@4842 268 }
kaf24@4842 269 #else
kaf24@4842 270 int __bitmap_weight(const unsigned long *bitmap, int bits)
kaf24@4842 271 {
kaf24@4842 272 int k, w = 0, lim = bits/BITS_PER_LONG;
kaf24@4842 273
kaf24@4842 274 for (k = 0; k < lim; k++)
kaf24@4842 275 w += hweight64(bitmap[k]);
kaf24@4842 276
kaf24@4842 277 if (bits % BITS_PER_LONG)
kaf24@4842 278 w += hweight64(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
kaf24@4842 279
kaf24@4842 280 return w;
kaf24@4842 281 }
kaf24@4842 282 #endif
kaf24@4842 283 EXPORT_SYMBOL(__bitmap_weight);
kaf24@4842 284
kaf24@8550 285 /*
kaf24@8550 286 * Bitmap printing & parsing functions: first version by Bill Irwin,
kaf24@8550 287 * second version by Paul Jackson, third by Joe Korty.
kaf24@8550 288 */
kaf24@8550 289
kaf24@8550 290 #define CHUNKSZ 32
kaf24@8550 291 #define nbits_to_hold_value(val) fls(val)
kaf24@8550 292 #define roundup_power2(val,modulus) (((val) + (modulus) - 1) & ~((modulus) - 1))
kaf24@8550 293 #define unhex(c) (isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10))
kaf24@8550 294 #define BASEDEC 10 /* fancier cpuset lists input in decimal */
kaf24@8550 295
kaf24@8550 296 /**
kaf24@8550 297 * bitmap_scnprintf - convert bitmap to an ASCII hex string.
kaf24@8550 298 * @buf: byte buffer into which string is placed
kaf24@8550 299 * @buflen: reserved size of @buf, in bytes
kaf24@8550 300 * @maskp: pointer to bitmap to convert
kaf24@8550 301 * @nmaskbits: size of bitmap, in bits
kaf24@8550 302 *
kaf24@8550 303 * Exactly @nmaskbits bits are displayed. Hex digits are grouped into
kaf24@8550 304 * comma-separated sets of eight digits per set.
kaf24@8550 305 */
kaf24@8550 306 int bitmap_scnprintf(char *buf, unsigned int buflen,
kaf24@8550 307 const unsigned long *maskp, int nmaskbits)
kaf24@8550 308 {
kaf24@8550 309 int i, word, bit, len = 0;
kaf24@8550 310 unsigned long val;
kaf24@8550 311 const char *sep = "";
kaf24@8550 312 int chunksz;
kaf24@8550 313 u32 chunkmask;
kaf24@8550 314
kaf24@8550 315 chunksz = nmaskbits & (CHUNKSZ - 1);
kaf24@8550 316 if (chunksz == 0)
kaf24@8550 317 chunksz = CHUNKSZ;
kaf24@8550 318
kaf24@8550 319 i = roundup_power2(nmaskbits, CHUNKSZ) - CHUNKSZ;
kaf24@8550 320 for (; i >= 0; i -= CHUNKSZ) {
kaf24@8550 321 chunkmask = ((1ULL << chunksz) - 1);
kaf24@8550 322 word = i / BITS_PER_LONG;
kaf24@8550 323 bit = i % BITS_PER_LONG;
kaf24@8550 324 val = (maskp[word] >> bit) & chunkmask;
kaf24@8550 325 len += scnprintf(buf+len, buflen-len, "%s%0*lx", sep,
kaf24@8550 326 (chunksz+3)/4, val);
kaf24@8550 327 chunksz = CHUNKSZ;
kaf24@8550 328 sep = ",";
kaf24@8550 329 }
kaf24@8550 330 return len;
kaf24@8550 331 }
kaf24@8550 332 EXPORT_SYMBOL(bitmap_scnprintf);
kaf24@8550 333
kaf24@8550 334 /*
kaf24@8550 335 * bscnl_emit(buf, buflen, rbot, rtop, bp)
kaf24@8550 336 *
kaf24@8550 337 * Helper routine for bitmap_scnlistprintf(). Write decimal number
kaf24@8550 338 * or range to buf, suppressing output past buf+buflen, with optional
kaf24@8550 339 * comma-prefix. Return len of what would be written to buf, if it
kaf24@8550 340 * all fit.
kaf24@8550 341 */
kaf24@8550 342 static inline int bscnl_emit(char *buf, int buflen, int rbot, int rtop, int len)
kaf24@8550 343 {
kaf24@8550 344 if (len > 0)
kaf24@8550 345 len += scnprintf(buf + len, buflen - len, ",");
kaf24@8550 346 if (rbot == rtop)
kaf24@8550 347 len += scnprintf(buf + len, buflen - len, "%d", rbot);
kaf24@8550 348 else
kaf24@8550 349 len += scnprintf(buf + len, buflen - len, "%d-%d", rbot, rtop);
kaf24@8550 350 return len;
kaf24@8550 351 }
kaf24@8550 352
kaf24@8550 353 /**
kaf24@8550 354 * bitmap_scnlistprintf - convert bitmap to list format ASCII string
kaf24@8550 355 * @buf: byte buffer into which string is placed
kaf24@8550 356 * @buflen: reserved size of @buf, in bytes
kaf24@8550 357 * @maskp: pointer to bitmap to convert
kaf24@8550 358 * @nmaskbits: size of bitmap, in bits
kaf24@8550 359 *
kaf24@8550 360 * Output format is a comma-separated list of decimal numbers and
kaf24@8550 361 * ranges. Consecutively set bits are shown as two hyphen-separated
kaf24@8550 362 * decimal numbers, the smallest and largest bit numbers set in
kaf24@8550 363 * the range. Output format is compatible with the format
kaf24@8550 364 * accepted as input by bitmap_parselist().
kaf24@8550 365 *
kaf24@8550 366 * The return value is the number of characters which would be
kaf24@8550 367 * generated for the given input, excluding the trailing '\0', as
kaf24@8550 368 * per ISO C99.
kaf24@8550 369 */
kaf24@8550 370 int bitmap_scnlistprintf(char *buf, unsigned int buflen,
kaf24@8550 371 const unsigned long *maskp, int nmaskbits)
kaf24@8550 372 {
kaf24@8550 373 int len = 0;
kaf24@8550 374 /* current bit is 'cur', most recently seen range is [rbot, rtop] */
kaf24@8550 375 int cur, rbot, rtop;
kaf24@8550 376
kaf24@8550 377 rbot = cur = find_first_bit(maskp, nmaskbits);
kaf24@8550 378 while (cur < nmaskbits) {
kaf24@8550 379 rtop = cur;
kaf24@8550 380 cur = find_next_bit(maskp, nmaskbits, cur+1);
kaf24@8550 381 if (cur >= nmaskbits || cur > rtop + 1) {
kaf24@8550 382 len = bscnl_emit(buf, buflen, rbot, rtop, len);
kaf24@8550 383 rbot = cur;
kaf24@8550 384 }
kaf24@8550 385 }
kaf24@8550 386 return len;
kaf24@8550 387 }
kaf24@8550 388 EXPORT_SYMBOL(bitmap_scnlistprintf);
kaf24@8550 389
kaf24@4842 390 /**
kaf24@4842 391 * bitmap_find_free_region - find a contiguous aligned mem region
kaf24@4842 392 * @bitmap: an array of unsigned longs corresponding to the bitmap
kaf24@4842 393 * @bits: number of bits in the bitmap
kaf24@4842 394 * @order: region size to find (size is actually 1<<order)
kaf24@4842 395 *
kaf24@4842 396 * This is used to allocate a memory region from a bitmap. The idea is
kaf24@4842 397 * that the region has to be 1<<order sized and 1<<order aligned (this
kaf24@4842 398 * makes the search algorithm much faster).
kaf24@4842 399 *
kaf24@4842 400 * The region is marked as set bits in the bitmap if a free one is
kaf24@4842 401 * found.
kaf24@4842 402 *
kaf24@4842 403 * Returns either beginning of region or negative error
kaf24@4842 404 */
kaf24@4842 405 int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
kaf24@4842 406 {
kaf24@4842 407 unsigned long mask;
kaf24@4842 408 int pages = 1 << order;
kaf24@4842 409 int i;
kaf24@4842 410
kaf24@4842 411 if(pages > BITS_PER_LONG)
kaf24@4842 412 return -EINVAL;
kaf24@4842 413
kaf24@4842 414 /* make a mask of the order */
kaf24@4842 415 mask = (1ul << (pages - 1));
kaf24@4842 416 mask += mask - 1;
kaf24@4842 417
kaf24@4842 418 /* run up the bitmap pages bits at a time */
kaf24@4842 419 for (i = 0; i < bits; i += pages) {
kaf24@4842 420 int index = i/BITS_PER_LONG;
kaf24@4842 421 int offset = i - (index * BITS_PER_LONG);
kaf24@4842 422 if((bitmap[index] & (mask << offset)) == 0) {
kaf24@4842 423 /* set region in bimap */
kaf24@4842 424 bitmap[index] |= (mask << offset);
kaf24@4842 425 return i;
kaf24@4842 426 }
kaf24@4842 427 }
kaf24@4842 428 return -ENOMEM;
kaf24@4842 429 }
kaf24@4842 430 EXPORT_SYMBOL(bitmap_find_free_region);
kaf24@4842 431
kaf24@4842 432 /**
kaf24@4842 433 * bitmap_release_region - release allocated bitmap region
kaf24@4842 434 * @bitmap: a pointer to the bitmap
kaf24@4842 435 * @pos: the beginning of the region
kaf24@4842 436 * @order: the order of the bits to release (number is 1<<order)
kaf24@4842 437 *
kaf24@4842 438 * This is the complement to __bitmap_find_free_region and releases
kaf24@4842 439 * the found region (by clearing it in the bitmap).
kaf24@4842 440 */
kaf24@4842 441 void bitmap_release_region(unsigned long *bitmap, int pos, int order)
kaf24@4842 442 {
kaf24@4842 443 int pages = 1 << order;
kaf24@4842 444 unsigned long mask = (1ul << (pages - 1));
kaf24@4842 445 int index = pos/BITS_PER_LONG;
kaf24@4842 446 int offset = pos - (index * BITS_PER_LONG);
kaf24@4842 447 mask += mask - 1;
kaf24@4842 448 bitmap[index] &= ~(mask << offset);
kaf24@4842 449 }
kaf24@4842 450 EXPORT_SYMBOL(bitmap_release_region);
kaf24@4842 451
kaf24@4842 452 int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
kaf24@4842 453 {
kaf24@4842 454 int pages = 1 << order;
kaf24@4842 455 unsigned long mask = (1ul << (pages - 1));
kaf24@4842 456 int index = pos/BITS_PER_LONG;
kaf24@4842 457 int offset = pos - (index * BITS_PER_LONG);
kaf24@4842 458
kaf24@4842 459 /* We don't do regions of pages > BITS_PER_LONG. The
kaf24@4842 460 * algorithm would be a simple look for multiple zeros in the
kaf24@4842 461 * array, but there's no driver today that needs this. If you
kaf24@4842 462 * trip this BUG(), you get to code it... */
kaf24@4842 463 BUG_ON(pages > BITS_PER_LONG);
kaf24@4842 464 mask += mask - 1;
kaf24@4842 465 if (bitmap[index] & (mask << offset))
kaf24@4842 466 return -EBUSY;
kaf24@4842 467 bitmap[index] |= (mask << offset);
kaf24@4842 468 return 0;
kaf24@4842 469 }
kaf24@4842 470 EXPORT_SYMBOL(bitmap_allocate_region);
kfraser@13540 471
kfraser@13540 472 #ifdef __BIG_ENDIAN
kfraser@13540 473
kfraser@13540 474 void bitmap_long_to_byte(uint8_t *bp, const unsigned long *lp, int nbits)
kfraser@13540 475 {
kfraser@13540 476 unsigned long l;
kfraser@13540 477 int i, j, b;
kfraser@13540 478
kfraser@13540 479 for (i = 0, b = 0; nbits > 0; i++, b += sizeof(l)) {
kfraser@13540 480 l = lp[i];
kfraser@13540 481 for (j = 0; (j < sizeof(l)) && (nbits > 0); j++) {
kfraser@13540 482 bp[b+j] = l;
kfraser@13540 483 l >>= 8;
kfraser@13540 484 nbits -= 8;
kfraser@13540 485 }
kfraser@13540 486 }
kfraser@13540 487 }
kfraser@13540 488
kfraser@13540 489 void bitmap_byte_to_long(unsigned long *lp, const uint8_t *bp, int nbits)
kfraser@13540 490 {
kfraser@13540 491 unsigned long l;
kfraser@13540 492 int i, j, b;
kfraser@13540 493
kfraser@13540 494 for (i = 0, b = 0; nbits > 0; i++, b += sizeof(l)) {
kfraser@13540 495 l = 0;
kfraser@13540 496 for (j = 0; (j < sizeof(l)) && (nbits > 0); j++) {
kaf24@13575 497 l |= (unsigned long)bp[b+j] << (j*8);
kfraser@13540 498 nbits -= 8;
kfraser@13540 499 }
kfraser@13540 500 lp[i] = l;
kfraser@13540 501 }
kfraser@13540 502 }
kfraser@13540 503
kfraser@13540 504 #elif defined(__LITTLE_ENDIAN)
kfraser@13540 505
kfraser@13540 506 void bitmap_long_to_byte(uint8_t *bp, const unsigned long *lp, int nbits)
kfraser@13540 507 {
kfraser@13540 508 memcpy(bp, lp, (nbits+7)/8);
kfraser@13540 509 }
kfraser@13540 510
kfraser@13540 511 void bitmap_byte_to_long(unsigned long *lp, const uint8_t *bp, int nbits)
kfraser@13540 512 {
kfraser@13540 513 /* We may need to pad the final longword with zeroes. */
kfraser@13540 514 if (nbits & (BITS_PER_LONG-1))
kfraser@13540 515 lp[BITS_TO_LONGS(nbits)-1] = 0;
kfraser@13540 516 memcpy(lp, bp, (nbits+7)/8);
kfraser@13540 517 }
kfraser@13540 518
kfraser@13540 519 #endif