Bit ops/bit masks
authorRonald G. Minnich <rminnich@google.com>
Thu, 13 Feb 2014 01:44:20 +0000 (17:44 -0800)
committerRonald G. Minnich <rminnich@google.com>
Thu, 13 Feb 2014 01:44:20 +0000 (17:44 -0800)
Wow, this turned into a saga.

What I'd like to do long term is figure out which of the gcc builtin ops
we could use and get rid of this nonsense, but that's a project for another
day. I did end up using __builtin_popcount, let's hope it actually works.
But by using that I got to NOT use some really awful stuff from the Linux
kernel that I never want to look at again.

This is reasonably good stuff from Linux, otherwise.

I'm turning off the vmx stuff for now because I'm doing some testing with Another
System and the two collide. The vm bits will no longer compile until some rework
is done on them anyway. Sorry.

Signed-off-by: Ronald G. Minnich <rminnich@google.com>
14 files changed:
kern/arch/x86/Kbuild
kern/arch/x86/arch.h
kern/arch/x86/bitops.h
kern/arch/x86/virtext.h [new file with mode: 0644]
kern/drivers/dev/Kbuild
kern/include/bitmap.h [new file with mode: 0644]
kern/include/bitops.h [new file with mode: 0644]
kern/include/env.h
kern/include/ros/common.h
kern/include/smp.h
kern/src/Kbuild
kern/src/bitmap.c [new file with mode: 0644]
kern/src/find_last_bit.c [new file with mode: 0644]
kern/src/find_next_bit.c [new file with mode: 0644]

index ab8982e..03c4f4a 100644 (file)
@@ -22,5 +22,5 @@ obj-y                                         += smp_boot.o
 obj-y                                          += smp_entry$(BITS).o
 obj-y                                          += trap.o trap$(BITS).o
 obj-y                                          += trapentry$(BITS).o
-obj-y                                          += vmx.o
-obj-y                                          += vmx_mmu.o
+#obj-y                                         += vmx.o
+#obj-y                                         += vmx_mmu.o
index 89f35c4..932f30e 100644 (file)
@@ -9,6 +9,7 @@
 /* Arch Constants */
 #define ARCH_CL_SIZE                            64
 
+#define __always_inline __attribute__((always_inline))
 static inline void breakpoint(void) __attribute__((always_inline));
 static inline void invlpg(void *addr) __attribute__((always_inline));  
 static inline void tlbflush(void) __attribute__((always_inline));
index 33a00bf..c1567ec 100644 (file)
@@ -1,5 +1,5 @@
-#ifndef _ASM_X86_BITOPS_H
-#define _ASM_X86_BITOPS_H
+#ifndef _X86_BITOPS_H
+#define _X86_BITOPS_H
 
 /*
  * Copyright 1992, Linus Torvalds.
@@ -7,16 +7,12 @@
  * Note: inlines with more than a single statement should be marked
  * __always_inline to avoid problems with older gcc's inlining heuristics.
  */
-
-#ifndef _LINUX_BITOPS_H
-#error only <linux/bitops.h> can be included directly
-#endif
-
-#include <linux/compiler.h>
-#include <asm/alternative.h>
+// barrier? Where is that defined? 
+#define barrier()
 
 #define BIT_64(n)                      (U64_C(1) << (n))
-
+#define DECLARE_BITMAP(name,bits) \
+       unsigned long name[(bits+sizeof(unsigned long)*8 - 1)/(sizeof(unsigned long)*8)/*BITS_TO_LONGS(bits)*/]
 /*
  * These have to be done with inline assembly: that way the bit-setting
  * is guaranteed to be atomic. All bit operations return 0 if the bit
  */
 
 #if __GNUC__ < 4 || (__GNUC__ == 4 && __GNUC_MINOR__ < 1)
-/* Technically wrong, but this avoids compilation errors on some gcc
-   versions. */
-#define BITOP_ADDR(x) "=m" (*(volatile long *) (x))
+#error "Get a gcc newer than 4.4.0"
 #else
 #define BITOP_ADDR(x) "+m" (*(volatile long *) (x))
 #endif
 
 #define ADDR                           BITOP_ADDR(addr)
 
+/* no idea what to really do about this */
+#define LOCK_PREFIX
 /*
  * We do the locked ops that don't return the old value as
  * a mask operation on a byte.
@@ -62,12 +58,13 @@ static __always_inline void
 set_bit(unsigned int nr, volatile unsigned long *addr)
 {
        if (IS_IMMEDIATE(nr)) {
-               asm volatile (LOCK_PREFIX "orb %1,%0":CONST_MASK_ADDR(nr, addr)
-                                         :"iq"((u8) CONST_MASK(nr))
-                                         :"memory");
+               asm volatile(LOCK_PREFIX "orb %1,%0"
+                       : CONST_MASK_ADDR(nr, addr)
+                       : "iq" ((uint8_t)CONST_MASK(nr))
+                       : "memory");
        } else {
-               asm volatile (LOCK_PREFIX
-                                         "bts %1,%0":BITOP_ADDR(addr):"Ir"(nr):"memory");
+               asm volatile(LOCK_PREFIX "bts %1,%0"
+                       : BITOP_ADDR(addr) : "Ir" (nr) : "memory");
        }
 }
 
@@ -82,7 +79,7 @@ set_bit(unsigned int nr, volatile unsigned long *addr)
  */
 static inline void __set_bit(int nr, volatile unsigned long *addr)
 {
-       asm volatile ("bts %1,%0":ADDR:"Ir"(nr):"memory");
+       asm volatile("bts %1,%0" : ADDR : "Ir" (nr) : "memory");
 }
 
 /**
@@ -95,14 +92,17 @@ static inline void __set_bit(int nr, volatile unsigned long *addr)
  * you should call smp_mb__before_clear_bit() and/or smp_mb__after_clear_bit()
  * in order to ensure changes are visible on other processors.
  */
-static __always_inline void clear_bit(int nr, volatile unsigned long *addr)
+static __always_inline void
+clear_bit(int nr, volatile unsigned long *addr)
 {
        if (IS_IMMEDIATE(nr)) {
-               asm volatile (LOCK_PREFIX "andb %1,%0":CONST_MASK_ADDR(nr, addr)
-                                         :"iq"((u8) ~ CONST_MASK(nr)));
+               asm volatile(LOCK_PREFIX "andb %1,%0"
+                       : CONST_MASK_ADDR(nr, addr)
+                       : "iq" ((uint8_t)~CONST_MASK(nr)));
        } else {
-               asm volatile (LOCK_PREFIX "btr %1,%0":BITOP_ADDR(addr)
-                                         :"Ir"(nr));
+               asm volatile(LOCK_PREFIX "btr %1,%0"
+                       : BITOP_ADDR(addr)
+                       : "Ir" (nr));
        }
 }
 
@@ -116,13 +116,13 @@ static __always_inline void clear_bit(int nr, volatile unsigned long *addr)
  */
 static inline void clear_bit_unlock(unsigned nr, volatile unsigned long *addr)
 {
-       barrier();
+  //barrier();
        clear_bit(nr, addr);
 }
 
 static inline void __clear_bit(int nr, volatile unsigned long *addr)
 {
-       asm volatile ("btr %1,%0":ADDR:"Ir"(nr));
+       asm volatile("btr %1,%0" : ADDR : "Ir" (nr));
 }
 
 /*
@@ -157,7 +157,7 @@ static inline void __clear_bit_unlock(unsigned nr, volatile unsigned long *addr)
  */
 static inline void __change_bit(int nr, volatile unsigned long *addr)
 {
-       asm volatile ("btc %1,%0":ADDR:"Ir"(nr));
+       asm volatile("btc %1,%0" : ADDR : "Ir" (nr));
 }
 
 /**
@@ -172,11 +172,13 @@ static inline void __change_bit(int nr, volatile unsigned long *addr)
 static inline void change_bit(int nr, volatile unsigned long *addr)
 {
        if (IS_IMMEDIATE(nr)) {
-               asm volatile (LOCK_PREFIX "xorb %1,%0":CONST_MASK_ADDR(nr, addr)
-                                         :"iq"((u8) CONST_MASK(nr)));
+               asm volatile(LOCK_PREFIX "xorb %1,%0"
+                       : CONST_MASK_ADDR(nr, addr)
+                       : "iq" ((uint8_t)CONST_MASK(nr)));
        } else {
-               asm volatile (LOCK_PREFIX "btc %1,%0":BITOP_ADDR(addr)
-                                         :"Ir"(nr));
+               asm volatile(LOCK_PREFIX "btc %1,%0"
+                       : BITOP_ADDR(addr)
+                       : "Ir" (nr));
        }
 }
 
@@ -192,8 +194,8 @@ static inline int test_and_set_bit(int nr, volatile unsigned long *addr)
 {
        int oldbit;
 
-       asm volatile (LOCK_PREFIX "bts %2,%1\n\t"
-                                 "sbb %0,%0":"=r"(oldbit), ADDR:"Ir"(nr):"memory");
+       asm volatile(LOCK_PREFIX "bts %2,%1\n\t"
+                    "sbb %0,%0" : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
 
        return oldbit;
 }
@@ -224,7 +226,10 @@ static inline int __test_and_set_bit(int nr, volatile unsigned long *addr)
 {
        int oldbit;
 
-asm("bts %2,%1\n\t" "sbb %0,%0": "=r"(oldbit), ADDR:"Ir"(nr));
+       asm("bts %2,%1\n\t"
+           "sbb %0,%0"
+           : "=r" (oldbit), ADDR
+           : "Ir" (nr));
        return oldbit;
 }
 
@@ -240,8 +245,9 @@ static inline int test_and_clear_bit(int nr, volatile unsigned long *addr)
 {
        int oldbit;
 
-       asm volatile (LOCK_PREFIX "btr %2,%1\n\t"
-                                 "sbb %0,%0":"=r"(oldbit), ADDR:"Ir"(nr):"memory");
+       asm volatile(LOCK_PREFIX "btr %2,%1\n\t"
+                    "sbb %0,%0"
+                    : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
 
        return oldbit;
 }
@@ -266,7 +272,10 @@ static inline int __test_and_clear_bit(int nr, volatile unsigned long *addr)
 {
        int oldbit;
 
-       asm volatile ("btr %2,%1\n\t" "sbb %0,%0":"=r" (oldbit), ADDR:"Ir"(nr));
+       asm volatile("btr %2,%1\n\t"
+                    "sbb %0,%0"
+                    : "=r" (oldbit), ADDR
+                    : "Ir" (nr));
        return oldbit;
 }
 
@@ -275,8 +284,10 @@ static inline int __test_and_change_bit(int nr, volatile unsigned long *addr)
 {
        int oldbit;
 
-       asm volatile ("btc %2,%1\n\t"
-                                 "sbb %0,%0":"=r" (oldbit), ADDR:"Ir"(nr):"memory");
+       asm volatile("btc %2,%1\n\t"
+                    "sbb %0,%0"
+                    : "=r" (oldbit), ADDR
+                    : "Ir" (nr) : "memory");
 
        return oldbit;
 }
@@ -293,42 +304,35 @@ static inline int test_and_change_bit(int nr, volatile unsigned long *addr)
 {
        int oldbit;
 
-       asm volatile (LOCK_PREFIX "btc %2,%1\n\t"
-                                 "sbb %0,%0":"=r"(oldbit), ADDR:"Ir"(nr):"memory");
+       asm volatile(LOCK_PREFIX "btc %2,%1\n\t"
+                    "sbb %0,%0"
+                    : "=r" (oldbit), ADDR : "Ir" (nr) : "memory");
 
        return oldbit;
 }
 
-static __always_inline int constant_test_bit(unsigned int nr,
-                                                                                        const volatile unsigned long *addr)
+static __always_inline int constant_test_bit(unsigned int nr, const volatile unsigned long *addr)
 {
-       return ((1UL << (nr % BITS_PER_LONG)) & (addr[nr / BITS_PER_LONG])) != 0;
+       return ((1UL << (nr % BITS_PER_LONG)) &
+               (addr[nr / BITS_PER_LONG])) != 0;
 }
 
 static inline int variable_test_bit(int nr, volatile const unsigned long *addr)
 {
        int oldbit;
 
-       asm volatile ("bt %2,%1\n\t" "sbb %0,%0":"=r" (oldbit)
-                                 :"m"(*(unsigned long *)addr), "Ir"(nr));
+       asm volatile("bt %2,%1\n\t"
+                    "sbb %0,%0"
+                    : "=r" (oldbit)
+                    : "m" (*(unsigned long *)addr), "Ir" (nr));
 
        return oldbit;
 }
 
-#if 0  /* Fool kernel-doc since it doesn't do macros yet */
-/**
- * test_bit - Determine whether a bit is set
- * @nr: bit number to test
- * @addr: Address to start counting from
- */
-static int test_bit(int nr, const volatile unsigned long *addr);
-#endif
-
-#define test_bit(nr, addr)                     \
-       (__builtin_constant_p((nr))             \
-        ? constant_test_bit((nr), (addr))      \
-        : variable_test_bit((nr), (addr)))
-
+#define test_bit(nr, addr)                      \
+        (__builtin_constant_p((nr))             \
+         ? constant_test_bit((nr), (addr))      \
+         : variable_test_bit((nr), (addr)))
 /**
  * __ffs - find first set bit in word
  * @word: The word to search
@@ -337,8 +341,9 @@ static int test_bit(int nr, const volatile unsigned long *addr);
  */
 static inline unsigned long __ffs(unsigned long word)
 {
-asm("rep; bsf %1,%0":"=r"(word)
-:              "rm"(word));
+       asm("rep; bsf %1,%0"
+               : "=r" (word)
+               : "rm" (word));
        return word;
 }
 
@@ -350,8 +355,9 @@ asm("rep; bsf %1,%0":"=r"(word)
  */
 static inline unsigned long ffz(unsigned long word)
 {
-asm("rep; bsf %1,%0":"=r"(word)
-:              "r"(~word));
+       asm("rep; bsf %1,%0"
+               : "=r" (word)
+               : "r" (~word));
        return word;
 }
 
@@ -363,14 +369,14 @@ asm("rep; bsf %1,%0":"=r"(word)
  */
 static inline unsigned long __fls(unsigned long word)
 {
-asm("bsr %1,%0":"=r"(word)
-:              "rm"(word));
+       asm("bsr %1,%0"
+           : "=r" (word)
+           : "rm" (word));
        return word;
 }
 
 #undef ADDR
 
-#ifdef __KERNEL__
 /**
  * ffs - find first set bit in word
  * @x: the word to search
@@ -396,12 +402,18 @@ static inline int ffs(int x)
         * We cannot do this on 32 bits because at the very least some
         * 486 CPUs did not behave this way.
         */
-asm("bsfl %1,%0":"=r"(r)
-:              "rm"(x), "0"(-1));
+       asm("bsfl %1,%0"
+           : "=r" (r)
+           : "rm" (x), "0" (-1));
 #elif defined(CONFIG_X86_CMOV)
-asm("bsfl %1,%0\n\t" "cmovzl %2,%0": "=&r"(r):"rm"(x), "r"(-1));
+       asm("bsfl %1,%0\n\t"
+           "cmovzl %2,%0"
+           : "=&r" (r) : "rm" (x), "r" (-1));
 #else
-asm("bsfl %1,%0\n\t" "jnz 1f\n\t" "movl $-1,%0\n" "1:": "=r"(r):"rm"(x));
+       asm("bsfl %1,%0\n\t"
+           "jnz 1f\n\t"
+           "movl $-1,%0\n"
+           "1:" : "=r" (r) : "rm" (x));
 #endif
        return r + 1;
 }
@@ -431,12 +443,18 @@ static inline int fls(int x)
         * We cannot do this on 32 bits because at the very least some
         * 486 CPUs did not behave this way.
         */
-asm("bsrl %1,%0":"=r"(r)
-:              "rm"(x), "0"(-1));
+       asm("bsrl %1,%0"
+           : "=r" (r)
+           : "rm" (x), "0" (-1));
 #elif defined(CONFIG_X86_CMOV)
-asm("bsrl %1,%0\n\t" "cmovzl %2,%0": "=&r"(r):"rm"(x), "rm"(-1));
+       asm("bsrl %1,%0\n\t"
+           "cmovzl %2,%0"
+           : "=&r" (r) : "rm" (x), "rm" (-1));
 #else
-asm("bsrl %1,%0\n\t" "jnz 1f\n\t" "movl $-1,%0\n" "1:": "=r"(r):"rm"(x));
+       asm("bsrl %1,%0\n\t"
+           "jnz 1f\n\t"
+           "movl $-1,%0\n"
+           "1:" : "=r" (r) : "rm" (x));
 #endif
        return r + 1;
 }
@@ -453,7 +471,7 @@ asm("bsrl %1,%0\n\t" "jnz 1f\n\t" "movl $-1,%0\n" "1:": "=r"(r):"rm"(x));
  * at position 64.
  */
 #ifdef CONFIG_X86_64
-static __always_inline int fls64(__u64 x)
+static __always_inline int fls64(uint64_t x)
 {
        int bitpos = -1;
        /*
@@ -461,27 +479,12 @@ static __always_inline int fls64(__u64 x)
         * dest reg is undefined if x==0, but their CPU architect says its
         * value is written to set it to the same as before.
         */
-asm("bsrq %1,%q0":"+r"(bitpos)
-:              "rm"(x));
+       asm("bsrq %1,%q0"
+           : "+r" (bitpos)
+           : "rm" (x));
        return bitpos + 1;
 }
 #else
-#include <asm-generic/bitops/fls64.h>
+#error "Need the generic version of fls64"
 #endif
-
-#include <asm-generic/bitops/find.h>
-
-#include <asm-generic/bitops/sched.h>
-
-#define ARCH_HAS_FAST_MULTIPLIER 1
-
-#include <asm/arch_hweight.h>
-
-#include <asm-generic/bitops/const_hweight.h>
-
-#include <asm-generic/bitops/le.h>
-
-#include <asm-generic/bitops/ext2-atomic-setbit.h>
-
-#endif /* __KERNEL__ */
 #endif /* _ASM_X86_BITOPS_H */
diff --git a/kern/arch/x86/virtext.h b/kern/arch/x86/virtext.h
new file mode 100644 (file)
index 0000000..75fb11b
--- /dev/null
@@ -0,0 +1,126 @@
+/* CPU virtualization extensions handling
+ *
+ * This should carry the code for handling CPU virtualization extensions
+ * that needs to live in the kernel core.
+ *
+ * Author: Eduardo Habkost <ehabkost@redhat.com>
+ *
+ * Copyright (C) 2008, Red Hat Inc.
+ *
+ * Contains code from KVM, Copyright (C) 2006 Qumranet, Inc.
+ *
+ * This work is licensed under the terms of the GNU GPL, version 2.  See
+ * the COPYING file in the top-level directory.
+ */
+#ifndef VIRTEX_H
+#define VIRTEX_H
+
+/*
+ * VMX functions:
+ */
+
+static inline int cpu_has_vmx(void)
+{
+       unsigned long ecx = cpuid_ecx(1);
+       return ecx & (1<<5); /* CPUID.1:ECX.VMX[bit 5] -> VT */
+}
+
+
+/** Disable VMX on the current CPU
+ *
+ * vmxoff causes a undefined-opcode exception if vmxon was not run
+ * on the CPU previously. Only call this function if you know VMX
+ * is enabled.
+ */
+static inline void cpu_vmxoff(void)
+{
+       asm volatile (ASM_VMX_VMXOFF : : : "cc");
+       lcr4(rcr4() & ~X86_CR4_VMXE);
+}
+
+static inline int cpu_vmx_enabled(void)
+{
+       return rcr4() & X86_CR4_VMXE;
+}
+
+/** Disable VMX if it is enabled on the current CPU
+ *
+ * You shouldn't call this if cpu_has_vmx() returns 0.
+ */
+static inline void __cpu_emergency_vmxoff(void)
+{
+       if (cpu_vmx_enabled())
+               cpu_vmxoff();
+}
+
+/** Disable VMX if it is supported and enabled on the current CPU
+ */
+static inline void cpu_emergency_vmxoff(void)
+{
+       if (cpu_has_vmx())
+               __cpu_emergency_vmxoff();
+}
+
+#if 0
+
+
+/*
+ * SVM functions:
+ */
+
+/** Check if the CPU has SVM support
+ *
+ * You can use the 'msg' arg to get a message describing the problem,
+ * if the function returns zero. Simply pass NULL if you are not interested
+ * on the messages; gcc should take care of not generating code for
+ * the messages on this case.
+ */
+static inline int cpu_has_svm(const char **msg)
+{
+       uint32_t eax, ebx, ecx, edx;
+
+       if (boot_cpu_data.x86_vendor != X86_VENDOR_AMD) {
+               if (msg)
+                       *msg = "not amd";
+               return 0;
+       }
+
+       cpuid(0x80000000, &eax, &ebx, &ecx, &edx);
+       if (eax < SVM_CPUID_FUNC) {
+               if (msg)
+                       *msg = "can't execute cpuid_8000000a";
+               return 0;
+       }
+
+       cpuid(0x80000001, &eax, &ebx, &ecx, &edx);
+       if (!(ecx & (1 << SVM_CPUID_FEATURE_SHIFT))) {
+               if (msg)
+                       *msg = "svm not available";
+               return 0;
+       }
+       return 1;
+}
+
+
+/** Disable SVM on the current CPU
+ *
+ * You should call this only if cpu_has_svm() returned true.
+ */
+static inline void cpu_svm_disable(void)
+{
+       uint64_t efer;
+
+       wrmsrl(MSR_VM_HSAVE_PA, 0);
+       rdmsrl(MSR_EFER, efer);
+       wrmsrl(MSR_EFER, efer & ~EFER_SVME);
+}
+
+/** Makes sure SVM is disabled, if it is supported on the CPU
+ */
+static inline void cpu_emergency_svm_disable(void)
+{
+       if (cpu_has_svm(NULL))
+               cpu_svm_disable();
+}
+#endif
+#endif /* _ASM_X86_VIRTEX_H */
index 13de845..cf556e2 100644 (file)
@@ -6,4 +6,4 @@ obj-y                                           += mnt.o
 obj-y                                          += pipe.o
 obj-y                                          += root.o
 obj-y                                          += srv.o
-obj-y                                          += vm.o
+#obj-y                                         += vm.o
diff --git a/kern/include/bitmap.h b/kern/include/bitmap.h
new file mode 100644 (file)
index 0000000..16cdd75
--- /dev/null
@@ -0,0 +1,300 @@
+#ifndef __LINUX_BITMAP_H
+#define __LINUX_BITMAP_H
+
+/*
+ * bitmaps provide bit arrays that consume one or more unsigned
+ * longs.  The bitmap interface and available operations are listed
+ * here, in bitmap.h
+ *
+ * Function implementations generic to all architectures are in
+ * lib/bitmap.c.  Functions implementations that are architecture
+ * specific are in various include/asm-<arch>/bitops.h headers
+ * and other arch/<arch> specific files.
+ *
+ * See lib/bitmap.c for more details.
+ */
+
+/*
+ * The available bitmap operations and their rough meaning in the
+ * case that the bitmap is a single unsigned long are thus:
+ *
+ * Note that nbits should be always a compile time evaluable constant.
+ * Otherwise many inlines will generate horrible code.
+ *
+ * bitmap_zero(dst, nbits)                     *dst = 0UL
+ * bitmap_fill(dst, nbits)                     *dst = ~0UL
+ * bitmap_copy(dst, src, nbits)                        *dst = *src
+ * bitmap_and(dst, src1, src2, nbits)          *dst = *src1 & *src2
+ * bitmap_or(dst, src1, src2, nbits)           *dst = *src1 | *src2
+ * bitmap_xor(dst, src1, src2, nbits)          *dst = *src1 ^ *src2
+ * bitmap_andnot(dst, src1, src2, nbits)       *dst = *src1 & ~(*src2)
+ * bitmap_complement(dst, src, nbits)          *dst = ~(*src)
+ * bitmap_equal(src1, src2, nbits)             Are *src1 and *src2 equal?
+ * bitmap_intersects(src1, src2, nbits)        Do *src1 and *src2 overlap?
+ * bitmap_subset(src1, src2, nbits)            Is *src1 a subset of *src2?
+ * bitmap_empty(src, nbits)                    Are all bits zero in *src?
+ * bitmap_full(src, nbits)                     Are all bits set in *src?
+ * bitmap_weight(src, nbits)                   Hamming Weight: number set bits
+ * bitmap_set(dst, pos, nbits)                 Set specified bit area
+ * bitmap_clear(dst, pos, nbits)               Clear specified bit area
+ * bitmap_find_next_zero_area(buf, len, pos, n, mask)  Find bit free area
+ * bitmap_shift_right(dst, src, n, nbits)      *dst = *src >> n
+ * bitmap_shift_left(dst, src, n, nbits)       *dst = *src << n
+ * bitmap_remap(dst, src, old, new, nbits)     *dst = map(old, new)(src)
+ * bitmap_bitremap(oldbit, old, new, nbits)    newbit = map(old, new)(oldbit)
+ * bitmap_onto(dst, orig, relmap, nbits)       *dst = orig relative to relmap
+ * bitmap_fold(dst, orig, sz, nbits)           dst bits = orig bits mod sz
+ * bitmap_scnprintf(buf, len, src, nbits)      Print bitmap src to buf
+ * bitmap_parse(buf, buflen, dst, nbits)       Parse bitmap dst from kernel buf
+ * bitmap_parse_user(ubuf, ulen, dst, nbits)   Parse bitmap dst from user buf
+ * bitmap_scnlistprintf(buf, len, src, nbits)  Print bitmap src as list to buf
+ * bitmap_parselist(buf, dst, nbits)           Parse bitmap dst from kernel buf
+ * bitmap_parselist_user(buf, dst, nbits)      Parse bitmap dst from user buf
+ * bitmap_find_free_region(bitmap, bits, order)        Find and allocate bit region
+ * bitmap_release_region(bitmap, pos, order)   Free specified bit region
+ * bitmap_allocate_region(bitmap, pos, order)  Allocate specified bit region
+ */
+
+/*
+ * Also the following operations in asm/bitops.h apply to bitmaps.
+ *
+ * set_bit(bit, addr)                  *addr |= bit
+ * clear_bit(bit, addr)                        *addr &= ~bit
+ * change_bit(bit, addr)               *addr ^= bit
+ * test_bit(bit, addr)                 Is bit set in *addr?
+ * test_and_set_bit(bit, addr)         Set bit and return old value
+ * test_and_clear_bit(bit, addr)       Clear bit and return old value
+ * test_and_change_bit(bit, addr)      Change bit and return old value
+ * find_first_zero_bit(addr, nbits)    Position first zero bit in *addr
+ * find_first_bit(addr, nbits)         Position first set bit in *addr
+ * find_next_zero_bit(addr, nbits, bit)        Position next zero bit in *addr >= bit
+ * find_next_bit(addr, nbits, bit)     Position next set bit in *addr >= bit
+ */
+
+/*
+ * The DECLARE_BITMAP(name,bits) macro, in linux/types.h, can be used
+ * to declare an array named 'name' of just enough unsigned longs to
+ * contain all bit positions from 0 to 'bits' - 1.
+ */
+
+/*
+ * lib/bitmap.c provides these functions:
+ */
+
+extern int __bitmap_empty(const unsigned long *bitmap, int bits);
+extern int __bitmap_full(const unsigned long *bitmap, int bits);
+extern int __bitmap_equal(const unsigned long *bitmap1,
+                       const unsigned long *bitmap2, int bits);
+extern void __bitmap_complement(unsigned long *dst, const unsigned long *src,
+                       int bits);
+extern void __bitmap_shift_right(unsigned long *dst,
+                        const unsigned long *src, int shift, int bits);
+extern void __bitmap_shift_left(unsigned long *dst,
+                        const unsigned long *src, int shift, int bits);
+extern int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
+                       const unsigned long *bitmap2, int bits);
+extern void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
+                       const unsigned long *bitmap2, int bits);
+extern void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
+                       const unsigned long *bitmap2, int bits);
+extern int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
+                       const unsigned long *bitmap2, int bits);
+extern int __bitmap_intersects(const unsigned long *bitmap1,
+                       const unsigned long *bitmap2, int bits);
+extern int __bitmap_subset(const unsigned long *bitmap1,
+                       const unsigned long *bitmap2, int bits);
+extern int __bitmap_weight(const unsigned long *bitmap, int bits);
+
+extern void bitmap_set(unsigned long *map, int i, int len);
+extern void bitmap_clear(unsigned long *map, int start, int nr);
+extern unsigned long bitmap_find_next_zero_area(unsigned long *map,
+                                        unsigned long size,
+                                        unsigned long start,
+                                        unsigned int nr,
+                                        unsigned long align_mask);
+
+extern int bitmap_scnprintf(char *buf, unsigned int len,
+                       const unsigned long *src, int nbits);
+extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user,
+                       unsigned long *dst, int nbits);
+extern int bitmap_parse_user(const char *ubuf, unsigned int ulen,
+                       unsigned long *dst, int nbits);
+extern int bitmap_scnlistprintf(char *buf, unsigned int len,
+                       const unsigned long *src, int nbits);
+extern int bitmap_parselist(const char *buf, unsigned long *maskp,
+                       int nmaskbits);
+extern int bitmap_parselist_user(const char *ubuf, unsigned int ulen,
+                       unsigned long *dst, int nbits);
+extern void bitmap_remap(unsigned long *dst, const unsigned long *src,
+               const unsigned long *old, const unsigned long *new, int bits);
+extern int bitmap_bitremap(int oldbit,
+               const unsigned long *old, const unsigned long *new, int bits);
+extern void bitmap_onto(unsigned long *dst, const unsigned long *orig,
+               const unsigned long *relmap, int bits);
+extern void bitmap_fold(unsigned long *dst, const unsigned long *orig,
+               int sz, int bits);
+extern int bitmap_find_free_region(unsigned long *bitmap, int bits, int order);
+extern void bitmap_release_region(unsigned long *bitmap, int pos, int order);
+extern int bitmap_allocate_region(unsigned long *bitmap, int pos, int order);
+extern void bitmap_copy_le(void *dst, const unsigned long *src, int nbits);
+extern int bitmap_ord_to_pos(const unsigned long *bitmap, int n, int bits);
+
+#define BITMAP_FIRST_WORD_MASK(start) (~0UL << ((start) % BITS_PER_LONG))
+#define BITMAP_LAST_WORD_MASK(nbits)                                   \
+(                                                                      \
+       ((nbits) % BITS_PER_LONG) ?                                     \
+               (1UL<<((nbits) % BITS_PER_LONG))-1 : ~0UL               \
+)
+
+#define small_const_nbits(nbits) \
+       (__builtin_constant_p(nbits) && (nbits) <= BITS_PER_LONG)
+
+static inline void bitmap_zero(unsigned long *dst, int nbits)
+{
+       if (small_const_nbits(nbits))
+               *dst = 0UL;
+       else {
+               int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
+               memset(dst, 0, len);
+       }
+}
+
+static inline void bitmap_fill(unsigned long *dst, int nbits)
+{
+       size_t nlongs = BITS_TO_LONGS(nbits);
+       if (!small_const_nbits(nbits)) {
+               int len = (nlongs - 1) * sizeof(unsigned long);
+               memset(dst, 0xff,  len);
+       }
+       dst[nlongs - 1] = BITMAP_LAST_WORD_MASK(nbits);
+}
+
+static inline void bitmap_copy(unsigned long *dst, const unsigned long *src,
+                       int nbits)
+{
+       if (small_const_nbits(nbits))
+               *dst = *src;
+       else {
+               int len = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
+               memcpy(dst, src, len);
+       }
+}
+
+static inline int bitmap_and(unsigned long *dst, const unsigned long *src1,
+                       const unsigned long *src2, int nbits)
+{
+       if (small_const_nbits(nbits))
+               return (*dst = *src1 & *src2) != 0;
+       return __bitmap_and(dst, src1, src2, nbits);
+}
+
+static inline void bitmap_or(unsigned long *dst, const unsigned long *src1,
+                       const unsigned long *src2, int nbits)
+{
+       if (small_const_nbits(nbits))
+               *dst = *src1 | *src2;
+       else
+               __bitmap_or(dst, src1, src2, nbits);
+}
+
+static inline void bitmap_xor(unsigned long *dst, const unsigned long *src1,
+                       const unsigned long *src2, int nbits)
+{
+       if (small_const_nbits(nbits))
+               *dst = *src1 ^ *src2;
+       else
+               __bitmap_xor(dst, src1, src2, nbits);
+}
+
+static inline int bitmap_andnot(unsigned long *dst, const unsigned long *src1,
+                       const unsigned long *src2, int nbits)
+{
+       if (small_const_nbits(nbits))
+               return (*dst = *src1 & ~(*src2)) != 0;
+       return __bitmap_andnot(dst, src1, src2, nbits);
+}
+
+static inline void bitmap_complement(unsigned long *dst, const unsigned long *src,
+                       int nbits)
+{
+       if (small_const_nbits(nbits))
+               *dst = ~(*src) & BITMAP_LAST_WORD_MASK(nbits);
+       else
+               __bitmap_complement(dst, src, nbits);
+}
+
+static inline int bitmap_equal(const unsigned long *src1,
+                       const unsigned long *src2, int nbits)
+{
+       if (small_const_nbits(nbits))
+               return ! ((*src1 ^ *src2) & BITMAP_LAST_WORD_MASK(nbits));
+       else
+               return __bitmap_equal(src1, src2, nbits);
+}
+
+static inline int bitmap_intersects(const unsigned long *src1,
+                       const unsigned long *src2, int nbits)
+{
+       if (small_const_nbits(nbits))
+               return ((*src1 & *src2) & BITMAP_LAST_WORD_MASK(nbits)) != 0;
+       else
+               return __bitmap_intersects(src1, src2, nbits);
+}
+
+static inline int bitmap_subset(const unsigned long *src1,
+                       const unsigned long *src2, int nbits)
+{
+       if (small_const_nbits(nbits))
+               return ! ((*src1 & ~(*src2)) & BITMAP_LAST_WORD_MASK(nbits));
+       else
+               return __bitmap_subset(src1, src2, nbits);
+}
+
+static inline int bitmap_empty(const unsigned long *src, int nbits)
+{
+       if (small_const_nbits(nbits))
+               return ! (*src & BITMAP_LAST_WORD_MASK(nbits));
+       else
+               return __bitmap_empty(src, nbits);
+}
+
+static inline int bitmap_full(const unsigned long *src, int nbits)
+{
+       if (small_const_nbits(nbits))
+               return ! (~(*src) & BITMAP_LAST_WORD_MASK(nbits));
+       else
+               return __bitmap_full(src, nbits);
+}
+
+static inline int bitmap_weight(const unsigned long *src, int nbits)
+{
+       if (small_const_nbits(nbits))
+               return hweight_long(*src & BITMAP_LAST_WORD_MASK(nbits));
+       return __bitmap_weight(src, nbits);
+}
+
+static inline void bitmap_shift_right(unsigned long *dst,
+                       const unsigned long *src, int n, int nbits)
+{
+       if (small_const_nbits(nbits))
+               *dst = *src >> n;
+       else
+               __bitmap_shift_right(dst, src, n, nbits);
+}
+
+static inline void bitmap_shift_left(unsigned long *dst,
+                       const unsigned long *src, int n, int nbits)
+{
+       if (small_const_nbits(nbits))
+               *dst = (*src << n) & BITMAP_LAST_WORD_MASK(nbits);
+       else
+               __bitmap_shift_left(dst, src, n, nbits);
+}
+
+static inline int bitmap_parse(const char *buf, unsigned int buflen,
+                       unsigned long *maskp, int nmaskbits)
+{
+       return __bitmap_parse(buf, buflen, 0, maskp, nmaskbits);
+}
+
+#endif /* __LINUX_BITMAP_H */
diff --git a/kern/include/bitops.h b/kern/include/bitops.h
new file mode 100644 (file)
index 0000000..71ee2b1
--- /dev/null
@@ -0,0 +1,126 @@
+#ifndef ROS_KERN_BITOPS_H
+#define ROS_KERN_BITOPS_H
+
+#define BIT(nr)                        (1UL << (nr))
+#define BIT_MASK(nr)           (1UL << ((nr) % BITS_PER_LONG))
+#define BIT_WORD(nr)           ((nr) / BITS_PER_LONG)
+#define BITS_PER_BYTE          8
+#define BITS_TO_LONGS(nr)      DIV_ROUND_UP(nr, BITS_PER_BYTE * sizeof(long))
+
+extern unsigned int __sw_hweight8(unsigned int w);
+extern unsigned int __sw_hweight16(unsigned int w);
+extern unsigned int __sw_hweight32(unsigned int w);
+extern unsigned long __sw_hweight64(uint64_t w);
+
+/* not clear where we want these defined. */
+unsigned long find_last_bit(const unsigned long *addr, unsigned long size);
+unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
+                           unsigned long offset);
+unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
+                                unsigned long offset);
+unsigned long find_first_bit(const unsigned long *addr, unsigned long size);
+unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size);
+
+#include <arch/bitops.h>
+
+#define for_each_set_bit(bit, addr, size) \
+       for ((bit) = find_first_bit((addr), (size));            \
+            (bit) < (size);                                    \
+            (bit) = find_next_bit((addr), (size), (bit) + 1))
+
+/* same as for_each_set_bit() but use bit as value to start with */
+#define for_each_set_bit_from(bit, addr, size) \
+       for ((bit) = find_next_bit((addr), (size), (bit));      \
+            (bit) < (size);                                    \
+            (bit) = find_next_bit((addr), (size), (bit) + 1))
+
+#define for_each_clear_bit(bit, addr, size) \
+       for ((bit) = find_first_zero_bit((addr), (size));       \
+            (bit) < (size);                                    \
+            (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
+
+/* same as for_each_clear_bit() but use bit as value to start with */
+#define for_each_clear_bit_from(bit, addr, size) \
+       for ((bit) = find_next_zero_bit((addr), (size), (bit)); \
+            (bit) < (size);                                    \
+            (bit) = find_next_zero_bit((addr), (size), (bit) + 1))
+
+static __inline__ int get_bitmask_order(unsigned int count)
+{
+       int order;
+
+       order = fls(count);
+       return order;   /* We could be slightly more clever with -1 here... */
+}
+
+static __inline__ int get_count_order(unsigned int count)
+{
+       int order;
+
+       order = fls(count) - 1;
+       if (count & (count - 1))
+               order++;
+       return order;
+}
+
+static inline unsigned long hweight_long(unsigned long w)
+{
+       return __builtin_popcount(w);
+       //return sizeof(w) == 4 ? hweight32(w) : hweight64(w);
+}
+
+// not used yet and I have other things I'm trying to do
+#if 0
+static inline bool BITMASK_IS_SET_IN_RANGE(uint8_t* m, size_t beg, size_t end)
+{
+       for(size_t i=beg; i<end; i++) {
+               if(!GET_BITMASK_BIT(m, i))
+                       return FALSE;
+       }
+       return TRUE;
+}
+
+static inline bool BITMASK_IS_CLR_IN_RANGE(uint8_t* m, size_t beg, size_t end)
+{
+       for(size_t i=beg; i<end; i++) {
+               if(GET_BITMASK_BIT(m, i))
+                       return FALSE;
+       }
+       return TRUE;
+}
+
+static inline void SET_BITMASK_RANGE(uint8_t* m, size_t beg, size_t end)
+{
+       for(size_t i=beg; i<end; i++) {
+               SET_BITMASK_BIT(m, i);
+       }
+}
+
+static inline void CLR_BITMASK_RANGE(uint8_t* m, size_t beg, size_t end)
+{
+       for(size_t i=beg; i<end; i++) {
+               CLR_BITMASK_BIT(m, i);
+       }
+}
+
+
+/* Runs *work on every bit in the bitmask, passing *work the value of the bit
+ * that is set.  Optionally clears the bit from the bitmask. 
+ *
+ * We need this to be a macro, so that the calling code doesn't need the
+ * address for work_fn.  This matters for code that has nested functions that
+ * use local variables, since taking the address of work_fn will force the
+ * compiler to put the function on the stack and incur icache coherency
+ * overheads. */
+#define BITMASK_FOREACH_SET(name, size, work_fn, clear)                        \
+{                                                                              \
+       for (int i = 0; i < (size); i++) {                                         \
+               bool present = GET_BITMASK_BIT((name), i);                             \
+               if (present && (clear))                                                \
+                       CLR_BITMASK_BIT_ATOMIC((name), i);                                 \
+               if (present)                                                           \
+                       (work_fn)(i);                                                      \
+       }                                                                          \
+}                                                                              
+#endif
+#endif /* ROS_KERN_BITOPS_H */
index 0b23c98..2283906 100644 (file)
@@ -100,6 +100,7 @@ struct proc {
        struct proc_alarm_set           alarmset;
        struct cv_lookup_tailq          abortable_sleepers;
        spinlock_t                                      abort_list_lock;
+       void *virtinfo;
 };
 
 /* Til we remove all Env references */
index feba4d3..5063567 100644 (file)
@@ -90,6 +90,7 @@ typedef unsigned long uintreg_t;
        __b;                                                                       \
 })
 
+#define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
 // Return the integer logarithm of the value provided rounded down
 static inline uintptr_t LOG2_DOWN(uintptr_t value)
 {
index 3ac6df4..835f7a8 100644 (file)
@@ -35,6 +35,9 @@ struct per_cpu_info {
         */
        struct vmcs *vmxarea;
        struct vmcs *vmcs;
+       pseudodesc_t host_gdt;
+       int vmx_enabled;
+       void *local_vcpu;
 #endif
        spinlock_t lock;
        /* Process management */
index 097a75d..de9079b 100644 (file)
@@ -2,6 +2,7 @@ obj-y                                           += alarm.o
 obj-y                                          += apipe.o
 obj-y                                          += arsc.o
 obj-y                                          += atomic.o
+obj-y                                          += bitmap.o
 obj-y                                          += blockdev.o
 obj-y                                          += colored_caches.o
 obj-y                                          += console.o
@@ -11,6 +12,8 @@ obj-y                                         += env.o
 obj-y                                          += err.o
 obj-y                                          += event.o
 obj-y                                          += ext2fs.o
+obj-y                                          += find_next_bit.o
+obj-y                                          += find_last_bit.o
 obj-y                                          += frontend.o
 obj-y                                          += hashtable.o
 obj-y                                          += hexdump.o
diff --git a/kern/src/bitmap.c b/kern/src/bitmap.c
new file mode 100644 (file)
index 0000000..9e64a0b
--- /dev/null
@@ -0,0 +1,1161 @@
+/*
+ * lib/bitmap.c
+ * Helper functions for bitmap.h.
+ *
+ * This source code is licensed under the GNU General Public License,
+ * Version 2.  See the file COPYING for more details.
+ */
+#include <arch/arch.h>
+#include <error.h>
+#include <atomic.h>
+#include <string.h>
+#include <assert.h>
+#include <bitops.h>
+#include <bitmap.h>
+
+#warning "find where something like __ALIGN_MASK is defined"
+#define __ALIGN_MASK(x, mask)       (((x) + (mask)) & ~(mask))
+/*
+ * bitmaps provide an array of bits, implemented using an an
+ * array of unsigned longs.  The number of valid bits in a
+ * given bitmap does _not_ need to be an exact multiple of
+ * BITS_PER_LONG.
+ *
+ * The possible unused bits in the last, partially used word
+ * of a bitmap are 'don't care'.  The implementation makes
+ * no particular effort to keep them zero.  It ensures that
+ * their value will not affect the results of any operation.
+ * The bitmap operations that return Boolean (bitmap_empty,
+ * for example) or scalar (bitmap_weight, for example) results
+ * carefully filter out these unused bits from impacting their
+ * results.
+ *
+ * These operations actually hold to a slightly stronger rule:
+ * if you don't input any bitmaps to these ops that have some
+ * unused bits set, then they won't output any set unused bits
+ * in output bitmaps.
+ *
+ * The byte ordering of bitmaps is more natural on little
+ * endian architectures.  See the big-endian headers
+ * include/asm-ppc64/bitops.h and include/asm-s390/bitops.h
+ * for the best explanations of this ordering.
+ */
+
+int __bitmap_empty(const unsigned long *bitmap, int bits)
+{
+       int k, lim = bits/BITS_PER_LONG;
+       for (k = 0; k < lim; ++k)
+               if (bitmap[k])
+                       return 0;
+
+       if (bits % BITS_PER_LONG)
+               if (bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
+                       return 0;
+
+       return 1;
+}
+
+int __bitmap_full(const unsigned long *bitmap, int bits)
+{
+       int k, lim = bits/BITS_PER_LONG;
+       for (k = 0; k < lim; ++k)
+               if (~bitmap[k])
+                       return 0;
+
+       if (bits % BITS_PER_LONG)
+               if (~bitmap[k] & BITMAP_LAST_WORD_MASK(bits))
+                       return 0;
+
+       return 1;
+}
+
+int __bitmap_equal(const unsigned long *bitmap1,
+               const unsigned long *bitmap2, int bits)
+{
+       int k, lim = bits/BITS_PER_LONG;
+       for (k = 0; k < lim; ++k)
+               if (bitmap1[k] != bitmap2[k])
+                       return 0;
+
+       if (bits % BITS_PER_LONG)
+               if ((bitmap1[k] ^ bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
+                       return 0;
+
+       return 1;
+}
+
+void __bitmap_complement(unsigned long *dst, const unsigned long *src, int bits)
+{
+       int k, lim = bits/BITS_PER_LONG;
+       for (k = 0; k < lim; ++k)
+               dst[k] = ~src[k];
+
+       if (bits % BITS_PER_LONG)
+               dst[k] = ~src[k] & BITMAP_LAST_WORD_MASK(bits);
+}
+
+/**
+ * __bitmap_shift_right - logical right shift of the bits in a bitmap
+ *   @dst : destination bitmap
+ *   @src : source bitmap
+ *   @shift : shift by this many bits
+ *   @bits : bitmap size, in bits
+ *
+ * Shifting right (dividing) means moving bits in the MS -> LS bit
+ * direction.  Zeros are fed into the vacated MS positions and the
+ * LS bits shifted off the bottom are lost.
+ */
+void __bitmap_shift_right(unsigned long *dst,
+                       const unsigned long *src, int shift, int bits)
+{
+       int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
+       int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
+       unsigned long mask = (1UL << left) - 1;
+       for (k = 0; off + k < lim; ++k) {
+               unsigned long upper, lower;
+
+               /*
+                * If shift is not word aligned, take lower rem bits of
+                * word above and make them the top rem bits of result.
+                */
+               if (!rem || off + k + 1 >= lim)
+                       upper = 0;
+               else {
+                       upper = src[off + k + 1];
+                       if (off + k + 1 == lim - 1 && left)
+                               upper &= mask;
+               }
+               lower = src[off + k];
+               if (left && off + k == lim - 1)
+                       lower &= mask;
+               dst[k] = upper << (BITS_PER_LONG - rem) | lower >> rem;
+               if (left && k == lim - 1)
+                       dst[k] &= mask;
+       }
+       if (off)
+               memset(&dst[lim - off], 0, off*sizeof(unsigned long));
+}
+
+
+/**
+ * __bitmap_shift_left - logical left shift of the bits in a bitmap
+ *   @dst : destination bitmap
+ *   @src : source bitmap
+ *   @shift : shift by this many bits
+ *   @bits : bitmap size, in bits
+ *
+ * Shifting left (multiplying) means moving bits in the LS -> MS
+ * direction.  Zeros are fed into the vacated LS bit positions
+ * and those MS bits shifted off the top are lost.
+ */
+
+void __bitmap_shift_left(unsigned long *dst,
+                       const unsigned long *src, int shift, int bits)
+{
+       int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
+       int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
+       for (k = lim - off - 1; k >= 0; --k) {
+               unsigned long upper, lower;
+
+               /*
+                * If shift is not word aligned, take upper rem bits of
+                * word below and make them the bottom rem bits of result.
+                */
+               if (rem && k > 0)
+                       lower = src[k - 1];
+               else
+                       lower = 0;
+               upper = src[k];
+               if (left && k == lim - 1)
+                       upper &= (1UL << left) - 1;
+               dst[k + off] = lower  >> (BITS_PER_LONG - rem) | upper << rem;
+               if (left && k + off == lim - 1)
+                       dst[k + off] &= (1UL << left) - 1;
+       }
+       if (off)
+               memset(dst, 0, off*sizeof(unsigned long));
+}
+
+int __bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
+                               const unsigned long *bitmap2, int bits)
+{
+       int k;
+       int nr = BITS_TO_LONGS(bits);
+       unsigned long result = 0;
+
+       for (k = 0; k < nr; k++)
+               result |= (dst[k] = bitmap1[k] & bitmap2[k]);
+       return result != 0;
+}
+
+void __bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
+                               const unsigned long *bitmap2, int bits)
+{
+       int k;
+       int nr = BITS_TO_LONGS(bits);
+
+       for (k = 0; k < nr; k++)
+               dst[k] = bitmap1[k] | bitmap2[k];
+}
+
+void __bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
+                               const unsigned long *bitmap2, int bits)
+{
+       int k;
+       int nr = BITS_TO_LONGS(bits);
+
+       for (k = 0; k < nr; k++)
+               dst[k] = bitmap1[k] ^ bitmap2[k];
+}
+
+int __bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
+                               const unsigned long *bitmap2, int bits)
+{
+       int k;
+       int nr = BITS_TO_LONGS(bits);
+       unsigned long result = 0;
+
+       for (k = 0; k < nr; k++)
+               result |= (dst[k] = bitmap1[k] & ~bitmap2[k]);
+       return result != 0;
+}
+
+int __bitmap_intersects(const unsigned long *bitmap1,
+                               const unsigned long *bitmap2, int bits)
+{
+       int k, lim = bits/BITS_PER_LONG;
+       for (k = 0; k < lim; ++k)
+               if (bitmap1[k] & bitmap2[k])
+                       return 1;
+
+       if (bits % BITS_PER_LONG)
+               if ((bitmap1[k] & bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
+                       return 1;
+       return 0;
+}
+
+int __bitmap_subset(const unsigned long *bitmap1,
+                               const unsigned long *bitmap2, int bits)
+{
+       int k, lim = bits/BITS_PER_LONG;
+       for (k = 0; k < lim; ++k)
+               if (bitmap1[k] & ~bitmap2[k])
+                       return 0;
+
+       if (bits % BITS_PER_LONG)
+               if ((bitmap1[k] & ~bitmap2[k]) & BITMAP_LAST_WORD_MASK(bits))
+                       return 0;
+       return 1;
+}
+
+int __bitmap_weight(const unsigned long *bitmap, int bits)
+{
+       int k, w = 0, lim = bits/BITS_PER_LONG;
+
+       for (k = 0; k < lim; k++)
+               w += hweight_long(bitmap[k]);
+
+       if (bits % BITS_PER_LONG)
+               w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
+
+       return w;
+}
+
+void bitmap_set(unsigned long *map, int start, int nr)
+{
+       unsigned long *p = map + BIT_WORD(start);
+       const int size = start + nr;
+       int bits_to_set = BITS_PER_LONG - (start % BITS_PER_LONG);
+       unsigned long mask_to_set = BITMAP_FIRST_WORD_MASK(start);
+
+       while (nr - bits_to_set >= 0) {
+               *p |= mask_to_set;
+               nr -= bits_to_set;
+               bits_to_set = BITS_PER_LONG;
+               mask_to_set = ~0UL;
+               p++;
+       }
+       if (nr) {
+               mask_to_set &= BITMAP_LAST_WORD_MASK(size);
+               *p |= mask_to_set;
+       }
+}
+
+void bitmap_clear(unsigned long *map, int start, int nr)
+{
+       unsigned long *p = map + BIT_WORD(start);
+       const int size = start + nr;
+       int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
+       unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
+
+       while (nr - bits_to_clear >= 0) {
+               *p &= ~mask_to_clear;
+               nr -= bits_to_clear;
+               bits_to_clear = BITS_PER_LONG;
+               mask_to_clear = ~0UL;
+               p++;
+       }
+       if (nr) {
+               mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
+               *p &= ~mask_to_clear;
+       }
+}
+
+/*
+ * bitmap_find_next_zero_area - find a contiguous aligned zero area
+ * @map: The address to base the search on
+ * @size: The bitmap size in bits
+ * @start: The bitnumber to start searching at
+ * @nr: The number of zeroed bits we're looking for
+ * @align_mask: Alignment mask for zero area
+ *
+ * The @align_mask should be one less than a power of 2; the effect is that
+ * the bit offset of all zero areas this function finds is multiples of that
+ * power of 2. A @align_mask of 0 means no alignment is required.
+ */
+unsigned long bitmap_find_next_zero_area(unsigned long *map,
+                                        unsigned long size,
+                                        unsigned long start,
+                                        unsigned int nr,
+                                        unsigned long align_mask)
+{
+       unsigned long index, end, i;
+again:
+       index = find_next_zero_bit(map, size, start);
+
+       /* Align allocation */
+       index = __ALIGN_MASK(index, align_mask);
+
+       end = index + nr;
+       if (end > size)
+               return end;
+       i = find_next_bit(map, end, index);
+       if (i < end) {
+               start = i + 1;
+               goto again;
+       }
+       return index;
+}
+
+/*
+ * Bitmap printing & parsing functions: first version by Nadia Yvette Chambers,
+ * second version by Paul Jackson, third by Joe Korty.
+ */
+
+#define CHUNKSZ                                32
+#define nbits_to_hold_value(val)       fls(val)
+#define BASEDEC 10             /* fancier cpuset lists input in decimal */
+#if 0 
+later
+/**
+ * bitmap_scnprintf - convert bitmap to an ASCII hex string.
+ * @buf: byte buffer into which string is placed
+ * @buflen: reserved size of @buf, in bytes
+ * @maskp: pointer to bitmap to convert
+ * @nmaskbits: size of bitmap, in bits
+ *
+ * Exactly @nmaskbits bits are displayed.  Hex digits are grouped into
+ * comma-separated sets of eight digits per set.  Returns the number of
+ * characters which were written to *buf, excluding the trailing \0.
+ */
+int bitmap_scnprintf(char *buf, unsigned int buflen,
+       const unsigned long *maskp, int nmaskbits)
+{
+       int i, word, bit, len = 0;
+       unsigned long val;
+       const char *sep = "";
+       int chunksz;
+       uint32_t chunkmask;
+
+       chunksz = nmaskbits & (CHUNKSZ - 1);
+       if (chunksz == 0)
+               chunksz = CHUNKSZ;
+
+       i = ALIGN(nmaskbits, CHUNKSZ) - CHUNKSZ;
+       for (; i >= 0; i -= CHUNKSZ) {
+               chunkmask = ((1ULL << chunksz) - 1);
+               word = i / BITS_PER_LONG;
+               bit = i % BITS_PER_LONG;
+               val = (maskp[word] >> bit) & chunkmask;
+               len += scnprintf(buf+len, buflen-len, "%s%0*lx", sep,
+                       (chunksz+3)/4, val);
+               chunksz = CHUNKSZ;
+               sep = ",";
+       }
+       return len;
+}
+
+/**
+ * __bitmap_parse - convert an ASCII hex string into a bitmap.
+ * @buf: pointer to buffer containing string.
+ * @buflen: buffer size in bytes.  If string is smaller than this
+ *    then it must be terminated with a \0.
+ * @is_user: location of buffer, 0 indicates kernel space
+ * @maskp: pointer to bitmap array that will contain result.
+ * @nmaskbits: size of bitmap, in bits.
+ *
+ * Commas group hex digits into chunks.  Each chunk defines exactly 32
+ * bits of the resultant bitmask.  No chunk may specify a value larger
+ * than 32 bits (%-EOVERFLOW), and if a chunk specifies a smaller value
+ * then leading 0-bits are prepended.  %-EINVAL is returned for illegal
+ * characters and for grouping errors such as "1,,5", ",44", "," and "".
+ * Leading and trailing whitespace accepted, but not embedded whitespace.
+ */
+int __bitmap_parse(const char *buf, unsigned int buflen,
+               int is_user, unsigned long *maskp,
+               int nmaskbits)
+{
+       int c, old_c, totaldigits, ndigits, nchunks, nbits;
+       uint32_t chunk;
+       const char *ubuf = (const char *)buf;
+
+       bitmap_zero(maskp, nmaskbits);
+
+       nchunks = nbits = totaldigits = c = 0;
+       do {
+               chunk = ndigits = 0;
+
+               /* Get the next chunk of the bitmap */
+               while (buflen) {
+                       old_c = c;
+                       if (is_user) {
+                               if (__get_user(c, ubuf++))
+                                       return -EFAULT;
+                       }
+                       else
+                               c = *buf++;
+                       buflen--;
+                       if (isspace(c))
+                               continue;
+
+                       /*
+                        * If the last character was a space and the current
+                        * character isn't '\0', we've got embedded whitespace.
+                        * This is a no-no, so throw an error.
+                        */
+                       if (totaldigits && c && isspace(old_c))
+                               return -EINVAL;
+
+                       /* A '\0' or a ',' signal the end of the chunk */
+                       if (c == '\0' || c == ',')
+                               break;
+
+                       if (!isxdigit(c))
+                               return -EINVAL;
+
+                       /*
+                        * Make sure there are at least 4 free bits in 'chunk'.
+                        * If not, this hexdigit will overflow 'chunk', so
+                        * throw an error.
+                        */
+                       if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
+                               return -EOVERFLOW;
+
+                       chunk = (chunk << 4) | hex_to_bin(c);
+                       ndigits++; totaldigits++;
+               }
+               if (ndigits == 0)
+                       return -EINVAL;
+               if (nchunks == 0 && chunk == 0)
+                       continue;
+
+               __bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits);
+               *maskp |= chunk;
+               nchunks++;
+               nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;
+               if (nbits > nmaskbits)
+                       return -EOVERFLOW;
+       } while (buflen && c == ',');
+
+       return 0;
+}
+
+/**
+ * bitmap_parse_user - convert an ASCII hex string in a user buffer into a bitmap
+ *
+ * @ubuf: pointer to user buffer containing string.
+ * @ulen: buffer size in bytes.  If string is smaller than this
+ *    then it must be terminated with a \0.
+ * @maskp: pointer to bitmap array that will contain result.
+ * @nmaskbits: size of bitmap, in bits.
+ *
+ * Wrapper for __bitmap_parse(), providing it with user buffer.
+ *
+ * We cannot have this as an inline function in bitmap.h because it needs
+ * linux/uaccess.h to get the access_ok() declaration and this causes
+ * cyclic dependencies.
+ */
+int bitmap_parse_user(const char __user *ubuf,
+                       unsigned int ulen, unsigned long *maskp,
+                       int nmaskbits)
+{
+       if (!access_ok(VERIFY_READ, ubuf, ulen))
+               return -EFAULT;
+       return __bitmap_parse((const char __force *)ubuf,
+                               ulen, 1, maskp, nmaskbits);
+
+}
+
+/*
+ * bscnl_emit(buf, buflen, rbot, rtop, bp)
+ *
+ * Helper routine for bitmap_scnlistprintf().  Write decimal number
+ * or range to buf, suppressing output past buf+buflen, with optional
+ * comma-prefix.  Return len of what was written to *buf, excluding the
+ * trailing \0.
+ */
+static inline int bscnl_emit(char *buf, int buflen, int rbot, int rtop, int len)
+{
+       if (len > 0)
+               len += scnprintf(buf + len, buflen - len, ",");
+       if (rbot == rtop)
+               len += scnprintf(buf + len, buflen - len, "%d", rbot);
+       else
+               len += scnprintf(buf + len, buflen - len, "%d-%d", rbot, rtop);
+       return len;
+}
+
+/**
+ * bitmap_scnlistprintf - convert bitmap to list format ASCII string
+ * @buf: byte buffer into which string is placed
+ * @buflen: reserved size of @buf, in bytes
+ * @maskp: pointer to bitmap to convert
+ * @nmaskbits: size of bitmap, in bits
+ *
+ * Output format is a comma-separated list of decimal numbers and
+ * ranges.  Consecutively set bits are shown as two hyphen-separated
+ * decimal numbers, the smallest and largest bit numbers set in
+ * the range.  Output format is compatible with the format
+ * accepted as input by bitmap_parselist().
+ *
+ * The return value is the number of characters which were written to *buf
+ * excluding the trailing '\0', as per ISO C99's scnprintf.
+ */
+int bitmap_scnlistprintf(char *buf, unsigned int buflen,
+       const unsigned long *maskp, int nmaskbits)
+{
+       int len = 0;
+       /* current bit is 'cur', most recently seen range is [rbot, rtop] */
+       int cur, rbot, rtop;
+
+       if (buflen == 0)
+               return 0;
+       buf[0] = 0;
+
+       rbot = cur = find_first_bit(maskp, nmaskbits);
+       while (cur < nmaskbits) {
+               rtop = cur;
+               cur = find_next_bit(maskp, nmaskbits, cur+1);
+               if (cur >= nmaskbits || cur > rtop + 1) {
+                       len = bscnl_emit(buf, buflen, rbot, rtop, len);
+                       rbot = cur;
+               }
+       }
+       return len;
+}
+
+/**
+ * __bitmap_parselist - convert list format ASCII string to bitmap
+ * @buf: read nul-terminated user string from this buffer
+ * @buflen: buffer size in bytes.  If string is smaller than this
+ *    then it must be terminated with a \0.
+ * @is_user: location of buffer, 0 indicates kernel space
+ * @maskp: write resulting mask here
+ * @nmaskbits: number of bits in mask to be written
+ *
+ * Input format is a comma-separated list of decimal numbers and
+ * ranges.  Consecutively set bits are shown as two hyphen-separated
+ * decimal numbers, the smallest and largest bit numbers set in
+ * the range.
+ *
+ * Returns 0 on success, -errno on invalid input strings.
+ * Error values:
+ *    %-EINVAL: second number in range smaller than first
+ *    %-EINVAL: invalid character in string
+ *    %-ERANGE: bit number specified too large for mask
+ */
+static int __bitmap_parselist(const char *buf, unsigned int buflen,
+               int is_user, unsigned long *maskp,
+               int nmaskbits)
+{
+       unsigned a, b;
+       int c, old_c, totaldigits;
+       const char __user __force *ubuf = (const char __user __force *)buf;
+       int exp_digit, in_range;
+
+       totaldigits = c = 0;
+       bitmap_zero(maskp, nmaskbits);
+       do {
+               exp_digit = 1;
+               in_range = 0;
+               a = b = 0;
+
+               /* Get the next cpu# or a range of cpu#'s */
+               while (buflen) {
+                       old_c = c;
+                       if (is_user) {
+                               if (__get_user(c, ubuf++))
+                                       return -EFAULT;
+                       } else
+                               c = *buf++;
+                       buflen--;
+                       if (isspace(c))
+                               continue;
+
+                       /*
+                        * If the last character was a space and the current
+                        * character isn't '\0', we've got embedded whitespace.
+                        * This is a no-no, so throw an error.
+                        */
+                       if (totaldigits && c && isspace(old_c))
+                               return -EINVAL;
+
+                       /* A '\0' or a ',' signal the end of a cpu# or range */
+                       if (c == '\0' || c == ',')
+                               break;
+
+                       if (c == '-') {
+                               if (exp_digit || in_range)
+                                       return -EINVAL;
+                               b = 0;
+                               in_range = 1;
+                               exp_digit = 1;
+                               continue;
+                       }
+
+                       if (!isdigit(c))
+                               return -EINVAL;
+
+                       b = b * 10 + (c - '0');
+                       if (!in_range)
+                               a = b;
+                       exp_digit = 0;
+                       totaldigits++;
+               }
+               if (!(a <= b))
+                       return -EINVAL;
+               if (b >= nmaskbits)
+                       return -ERANGE;
+               while (a <= b) {
+                       set_bit(a, maskp);
+                       a++;
+               }
+       } while (buflen && c == ',');
+       return 0;
+}
+
+int bitmap_parselist(const char *bp, unsigned long *maskp, int nmaskbits)
+{
+       char *nl  = strchr(bp, '\n');
+       int len;
+
+       if (nl)
+               len = nl - bp;
+       else
+               len = strlen(bp);
+
+       return __bitmap_parselist(bp, len, 0, maskp, nmaskbits);
+}
+
+
+/**
+ * bitmap_parselist_user()
+ *
+ * @ubuf: pointer to user buffer containing string.
+ * @ulen: buffer size in bytes.  If string is smaller than this
+ *    then it must be terminated with a \0.
+ * @maskp: pointer to bitmap array that will contain result.
+ * @nmaskbits: size of bitmap, in bits.
+ *
+ * Wrapper for bitmap_parselist(), providing it with user buffer.
+ *
+ * We cannot have this as an inline function in bitmap.h because it needs
+ * linux/uaccess.h to get the access_ok() declaration and this causes
+ * cyclic dependencies.
+ */
+int bitmap_parselist_user(const char __user *ubuf,
+                       unsigned int ulen, unsigned long *maskp,
+                       int nmaskbits)
+{
+       if (!access_ok(VERIFY_READ, ubuf, ulen))
+               return -EFAULT;
+       return __bitmap_parselist((const char __force *)ubuf,
+                                       ulen, 1, maskp, nmaskbits);
+}
+
+#endif
+/**
+ * bitmap_pos_to_ord - find ordinal of set bit at given position in bitmap
+ *     @buf: pointer to a bitmap
+ *     @pos: a bit position in @buf (0 <= @pos < @bits)
+ *     @bits: number of valid bit positions in @buf
+ *
+ * Map the bit at position @pos in @buf (of length @bits) to the
+ * ordinal of which set bit it is.  If it is not set or if @pos
+ * is not a valid bit position, map to -1.
+ *
+ * If for example, just bits 4 through 7 are set in @buf, then @pos
+ * values 4 through 7 will get mapped to 0 through 3, respectively,
+ * and other @pos values will get mapped to 0.  When @pos value 7
+ * gets mapped to (returns) @ord value 3 in this example, that means
+ * that bit 7 is the 3rd (starting with 0th) set bit in @buf.
+ *
+ * The bit positions 0 through @bits are valid positions in @buf.
+ */
+static int bitmap_pos_to_ord(const unsigned long *buf, int pos, int bits)
+{
+       int i, ord;
+
+       if (pos < 0 || pos >= bits || !test_bit(pos, buf))
+               return -1;
+
+       i = find_first_bit(buf, bits);
+       ord = 0;
+       while (i < pos) {
+               i = find_next_bit(buf, bits, i + 1);
+               ord++;
+       }
+       if (i != pos)
+               panic("%s: i %d != pos %d\n", __func__, i, pos);
+
+       return ord;
+}
+
+/**
+ * bitmap_ord_to_pos - find position of n-th set bit in bitmap
+ *     @buf: pointer to bitmap
+ *     @ord: ordinal bit position (n-th set bit, n >= 0)
+ *     @bits: number of valid bit positions in @buf
+ *
+ * Map the ordinal offset of bit @ord in @buf to its position in @buf.
+ * Value of @ord should be in range 0 <= @ord < weight(buf), else
+ * results are undefined.
+ *
+ * If for example, just bits 4 through 7 are set in @buf, then @ord
+ * values 0 through 3 will get mapped to 4 through 7, respectively,
+ * and all other @ord values return undefined values.  When @ord value 3
+ * gets mapped to (returns) @pos value 7 in this example, that means
+ * that the 3rd set bit (starting with 0th) is at position 7 in @buf.
+ *
+ * The bit positions 0 through @bits are valid positions in @buf.
+ */
+int bitmap_ord_to_pos(const unsigned long *buf, int ord, int bits)
+{
+       int pos = 0;
+
+       if (ord >= 0 && ord < bits) {
+               int i;
+
+               for (i = find_first_bit(buf, bits);
+                    i < bits && ord > 0;
+                    i = find_next_bit(buf, bits, i + 1))
+                       ord--;
+               if (i < bits && ord == 0)
+                       pos = i;
+       }
+
+       return pos;
+}
+
+/**
+ * bitmap_remap - Apply map defined by a pair of bitmaps to another bitmap
+ *     @dst: remapped result
+ *     @src: subset to be remapped
+ *     @old: defines domain of map
+ *     @new: defines range of map
+ *     @bits: number of bits in each of these bitmaps
+ *
+ * Let @old and @new define a mapping of bit positions, such that
+ * whatever position is held by the n-th set bit in @old is mapped
+ * to the n-th set bit in @new.  In the more general case, allowing
+ * for the possibility that the weight 'w' of @new is less than the
+ * weight of @old, map the position of the n-th set bit in @old to
+ * the position of the m-th set bit in @new, where m == n % w.
+ *
+ * If either of the @old and @new bitmaps are empty, or if @src and
+ * @dst point to the same location, then this routine copies @src
+ * to @dst.
+ *
+ * The positions of unset bits in @old are mapped to themselves
+ * (the identify map).
+ *
+ * Apply the above specified mapping to @src, placing the result in
+ * @dst, clearing any bits previously set in @dst.
+ *
+ * For example, lets say that @old has bits 4 through 7 set, and
+ * @new has bits 12 through 15 set.  This defines the mapping of bit
+ * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
+ * bit positions unchanged.  So if say @src comes into this routine
+ * with bits 1, 5 and 7 set, then @dst should leave with bits 1,
+ * 13 and 15 set.
+ */
+void bitmap_remap(unsigned long *dst, const unsigned long *src,
+               const unsigned long *old, const unsigned long *new,
+               int bits)
+{
+       int oldbit, w;
+
+       if (dst == src)         /* following doesn't handle inplace remaps */
+               return;
+       bitmap_zero(dst, bits);
+
+       w = bitmap_weight(new, bits);
+       for_each_set_bit(oldbit, src, bits) {
+               int n = bitmap_pos_to_ord(old, oldbit, bits);
+
+               if (n < 0 || w == 0)
+                       set_bit(oldbit, dst);   /* identity map */
+               else
+                       set_bit(bitmap_ord_to_pos(new, n % w, bits), dst);
+       }
+}
+
+/**
+ * bitmap_bitremap - Apply map defined by a pair of bitmaps to a single bit
+ *     @oldbit: bit position to be mapped
+ *     @old: defines domain of map
+ *     @new: defines range of map
+ *     @bits: number of bits in each of these bitmaps
+ *
+ * Let @old and @new define a mapping of bit positions, such that
+ * whatever position is held by the n-th set bit in @old is mapped
+ * to the n-th set bit in @new.  In the more general case, allowing
+ * for the possibility that the weight 'w' of @new is less than the
+ * weight of @old, map the position of the n-th set bit in @old to
+ * the position of the m-th set bit in @new, where m == n % w.
+ *
+ * The positions of unset bits in @old are mapped to themselves
+ * (the identify map).
+ *
+ * Apply the above specified mapping to bit position @oldbit, returning
+ * the new bit position.
+ *
+ * For example, lets say that @old has bits 4 through 7 set, and
+ * @new has bits 12 through 15 set.  This defines the mapping of bit
+ * position 4 to 12, 5 to 13, 6 to 14 and 7 to 15, and of all other
+ * bit positions unchanged.  So if say @oldbit is 5, then this routine
+ * returns 13.
+ */
+int bitmap_bitremap(int oldbit, const unsigned long *old,
+                               const unsigned long *new, int bits)
+{
+       int w = bitmap_weight(new, bits);
+       int n = bitmap_pos_to_ord(old, oldbit, bits);
+       if (n < 0 || w == 0)
+               return oldbit;
+       else
+               return bitmap_ord_to_pos(new, n % w, bits);
+}
+
+/**
+ * bitmap_onto - translate one bitmap relative to another
+ *     @dst: resulting translated bitmap
+ *     @orig: original untranslated bitmap
+ *     @relmap: bitmap relative to which translated
+ *     @bits: number of bits in each of these bitmaps
+ *
+ * Set the n-th bit of @dst iff there exists some m such that the
+ * n-th bit of @relmap is set, the m-th bit of @orig is set, and
+ * the n-th bit of @relmap is also the m-th _set_ bit of @relmap.
+ * (If you understood the previous sentence the first time your
+ * read it, you're overqualified for your current job.)
+ *
+ * In other words, @orig is mapped onto (surjectively) @dst,
+ * using the the map { <n, m> | the n-th bit of @relmap is the
+ * m-th set bit of @relmap }.
+ *
+ * Any set bits in @orig above bit number W, where W is the
+ * weight of (number of set bits in) @relmap are mapped nowhere.
+ * In particular, if for all bits m set in @orig, m >= W, then
+ * @dst will end up empty.  In situations where the possibility
+ * of such an empty result is not desired, one way to avoid it is
+ * to use the bitmap_fold() operator, below, to first fold the
+ * @orig bitmap over itself so that all its set bits x are in the
+ * range 0 <= x < W.  The bitmap_fold() operator does this by
+ * setting the bit (m % W) in @dst, for each bit (m) set in @orig.
+ *
+ * Example [1] for bitmap_onto():
+ *  Let's say @relmap has bits 30-39 set, and @orig has bits
+ *  1, 3, 5, 7, 9 and 11 set.  Then on return from this routine,
+ *  @dst will have bits 31, 33, 35, 37 and 39 set.
+ *
+ *  When bit 0 is set in @orig, it means turn on the bit in
+ *  @dst corresponding to whatever is the first bit (if any)
+ *  that is turned on in @relmap.  Since bit 0 was off in the
+ *  above example, we leave off that bit (bit 30) in @dst.
+ *
+ *  When bit 1 is set in @orig (as in the above example), it
+ *  means turn on the bit in @dst corresponding to whatever
+ *  is the second bit that is turned on in @relmap.  The second
+ *  bit in @relmap that was turned on in the above example was
+ *  bit 31, so we turned on bit 31 in @dst.
+ *
+ *  Similarly, we turned on bits 33, 35, 37 and 39 in @dst,
+ *  because they were the 4th, 6th, 8th and 10th set bits
+ *  set in @relmap, and the 4th, 6th, 8th and 10th bits of
+ *  @orig (i.e. bits 3, 5, 7 and 9) were also set.
+ *
+ *  When bit 11 is set in @orig, it means turn on the bit in
+ *  @dst corresponding to whatever is the twelfth bit that is
+ *  turned on in @relmap.  In the above example, there were
+ *  only ten bits turned on in @relmap (30..39), so that bit
+ *  11 was set in @orig had no affect on @dst.
+ *
+ * Example [2] for bitmap_fold() + bitmap_onto():
+ *  Let's say @relmap has these ten bits set:
+ *             40 41 42 43 45 48 53 61 74 95
+ *  (for the curious, that's 40 plus the first ten terms of the
+ *  Fibonacci sequence.)
+ *
+ *  Further lets say we use the following code, invoking
+ *  bitmap_fold() then bitmap_onto, as suggested above to
+ *  avoid the possitility of an empty @dst result:
+ *
+ *     unsigned long *tmp;     // a temporary bitmap's bits
+ *
+ *     bitmap_fold(tmp, orig, bitmap_weight(relmap, bits), bits);
+ *     bitmap_onto(dst, tmp, relmap, bits);
+ *
+ *  Then this table shows what various values of @dst would be, for
+ *  various @orig's.  I list the zero-based positions of each set bit.
+ *  The tmp column shows the intermediate result, as computed by
+ *  using bitmap_fold() to fold the @orig bitmap modulo ten
+ *  (the weight of @relmap).
+ *
+ *      @orig           tmp            @dst
+ *      0                0             40
+ *      1                1             41
+ *      9                9             95
+ *      10               0             40 (*)
+ *      1 3 5 7          1 3 5 7       41 43 48 61
+ *      0 1 2 3 4        0 1 2 3 4     40 41 42 43 45
+ *      0 9 18 27        0 9 8 7       40 61 74 95
+ *      0 10 20 30       0             40
+ *      0 11 22 33       0 1 2 3       40 41 42 43
+ *      0 12 24 36       0 2 4 6       40 42 45 53
+ *      78 102 211       1 2 8         41 42 74 (*)
+ *
+ * (*) For these marked lines, if we hadn't first done bitmap_fold()
+ *     into tmp, then the @dst result would have been empty.
+ *
+ * If either of @orig or @relmap is empty (no set bits), then @dst
+ * will be returned empty.
+ *
+ * If (as explained above) the only set bits in @orig are in positions
+ * m where m >= W, (where W is the weight of @relmap) then @dst will
+ * once again be returned empty.
+ *
+ * All bits in @dst not set by the above rule are cleared.
+ */
+void bitmap_onto(unsigned long *dst, const unsigned long *orig,
+                       const unsigned long *relmap, int bits)
+{
+       int n, m;               /* same meaning as in above comment */
+
+       if (dst == orig)        /* following doesn't handle inplace mappings */
+               return;
+       bitmap_zero(dst, bits);
+
+       /*
+        * The following code is a more efficient, but less
+        * obvious, equivalent to the loop:
+        *      for (m = 0; m < bitmap_weight(relmap, bits); m++) {
+        *              n = bitmap_ord_to_pos(orig, m, bits);
+        *              if (test_bit(m, orig))
+        *                      set_bit(n, dst);
+        *      }
+        */
+
+       m = 0;
+       for_each_set_bit(n, relmap, bits) {
+               /* m == bitmap_pos_to_ord(relmap, n, bits) */
+               if (test_bit(m, orig))
+                       set_bit(n, dst);
+               m++;
+       }
+}
+
+/**
+ * bitmap_fold - fold larger bitmap into smaller, modulo specified size
+ *     @dst: resulting smaller bitmap
+ *     @orig: original larger bitmap
+ *     @sz: specified size
+ *     @bits: number of bits in each of these bitmaps
+ *
+ * For each bit oldbit in @orig, set bit oldbit mod @sz in @dst.
+ * Clear all other bits in @dst.  See further the comment and
+ * Example [2] for bitmap_onto() for why and how to use this.
+ */
+void bitmap_fold(unsigned long *dst, const unsigned long *orig,
+                       int sz, int bits)
+{
+       int oldbit;
+
+       if (dst == orig)        /* following doesn't handle inplace mappings */
+               return;
+       bitmap_zero(dst, bits);
+
+       for_each_set_bit(oldbit, orig, bits)
+               set_bit(oldbit % sz, dst);
+}
+
+/*
+ * Common code for bitmap_*_region() routines.
+ *     bitmap: array of unsigned longs corresponding to the bitmap
+ *     pos: the beginning of the region
+ *     order: region size (log base 2 of number of bits)
+ *     reg_op: operation(s) to perform on that region of bitmap
+ *
+ * Can set, verify and/or release a region of bits in a bitmap,
+ * depending on which combination of REG_OP_* flag bits is set.
+ *
+ * A region of a bitmap is a sequence of bits in the bitmap, of
+ * some size '1 << order' (a power of two), aligned to that same
+ * '1 << order' power of two.
+ *
+ * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
+ * Returns 0 in all other cases and reg_ops.
+ */
+
+enum {
+       REG_OP_ISFREE,          /* true if region is all zero bits */
+       REG_OP_ALLOC,           /* set all bits in region */
+       REG_OP_RELEASE,         /* clear all bits in region */
+};
+
+static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op)
+{
+       int nbits_reg;          /* number of bits in region */
+       int index;              /* index first long of region in bitmap */
+       int offset;             /* bit offset region in bitmap[index] */
+       int nlongs_reg;         /* num longs spanned by region in bitmap */
+       int nbitsinlong;        /* num bits of region in each spanned long */
+       unsigned long mask;     /* bitmask for one long of region */
+       int i;                  /* scans bitmap by longs */
+       int ret = 0;            /* return value */
+
+       /*
+        * Either nlongs_reg == 1 (for small orders that fit in one long)
+        * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
+        */
+       nbits_reg = 1 << order;
+       index = pos / BITS_PER_LONG;
+       offset = pos - (index * BITS_PER_LONG);
+       nlongs_reg = BITS_TO_LONGS(nbits_reg);
+       nbitsinlong = MIN(nbits_reg,  BITS_PER_LONG);
+
+       /*
+        * Can't do "mask = (1UL << nbitsinlong) - 1", as that
+        * overflows if nbitsinlong == BITS_PER_LONG.
+        */
+       mask = (1UL << (nbitsinlong - 1));
+       mask += mask - 1;
+       mask <<= offset;
+
+       switch (reg_op) {
+       case REG_OP_ISFREE:
+               for (i = 0; i < nlongs_reg; i++) {
+                       if (bitmap[index + i] & mask)
+                               goto done;
+               }
+               ret = 1;        /* all bits in region free (zero) */
+               break;
+
+       case REG_OP_ALLOC:
+               for (i = 0; i < nlongs_reg; i++)
+                       bitmap[index + i] |= mask;
+               break;
+
+       case REG_OP_RELEASE:
+               for (i = 0; i < nlongs_reg; i++)
+                       bitmap[index + i] &= ~mask;
+               break;
+       }
+done:
+       return ret;
+}
+
+/**
+ * bitmap_find_free_region - find a contiguous aligned mem region
+ *     @bitmap: array of unsigned longs corresponding to the bitmap
+ *     @bits: number of bits in the bitmap
+ *     @order: region size (log base 2 of number of bits) to find
+ *
+ * Find a region of free (zero) bits in a @bitmap of @bits bits and
+ * allocate them (set them to one).  Only consider regions of length
+ * a power (@order) of two, aligned to that power of two, which
+ * makes the search algorithm much faster.
+ *
+ * Return the bit offset in bitmap of the allocated region,
+ * or -errno on failure.
+ */
+int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
+{
+       int pos, end;           /* scans bitmap by regions of size order */
+
+       for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) {
+               if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
+                       continue;
+               __reg_op(bitmap, pos, order, REG_OP_ALLOC);
+               return pos;
+       }
+       return -ENOMEM;
+}
+
+/**
+ * bitmap_release_region - release allocated bitmap region
+ *     @bitmap: array of unsigned longs corresponding to the bitmap
+ *     @pos: beginning of bit region to release
+ *     @order: region size (log base 2 of number of bits) to release
+ *
+ * This is the complement to __bitmap_find_free_region() and releases
+ * the found region (by clearing it in the bitmap).
+ *
+ * No return value.
+ */
+void bitmap_release_region(unsigned long *bitmap, int pos, int order)
+{
+       __reg_op(bitmap, pos, order, REG_OP_RELEASE);
+}
+
+/**
+ * bitmap_allocate_region - allocate bitmap region
+ *     @bitmap: array of unsigned longs corresponding to the bitmap
+ *     @pos: beginning of bit region to allocate
+ *     @order: region size (log base 2 of number of bits) to allocate
+ *
+ * Allocate (set bits in) a specified region of a bitmap.
+ *
+ * Return 0 on success, or %-EBUSY if specified region wasn't
+ * free (not all bits were zero).
+ */
+int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
+{
+       if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
+               return -EBUSY;
+       __reg_op(bitmap, pos, order, REG_OP_ALLOC);
+       return 0;
+}
+
+#if 0
+/**
+ * bitmap_copy_le - copy a bitmap, putting the bits into little-endian order.
+ * @dst:   destination buffer
+ * @src:   bitmap to copy
+ * @nbits: number of bits in the bitmap
+ *
+ * Require nbits % BITS_PER_LONG == 0.
+ */
+void bitmap_copy_le(void *dst, const unsigned long *src, int nbits)
+{
+       unsigned long *d = dst;
+       int i;
+
+       for (i = 0; i < nbits/BITS_PER_LONG; i++) {
+               if (BITS_PER_LONG == 64)
+                       d[i] = cpu_to_le64(src[i]);
+               else
+                       d[i] = cpu_to_le32(src[i]);
+       }
+}
+#endif
diff --git a/kern/src/find_last_bit.c b/kern/src/find_last_bit.c
new file mode 100644 (file)
index 0000000..e93ed37
--- /dev/null
@@ -0,0 +1,48 @@
+/* find_last_bit.c: fallback find next bit implementation
+ *
+ * Copyright (C) 2008 IBM Corporation
+ * Written by Rusty Russell <rusty@rustcorp.com.au>
+ * (Inspired by David Howell's find_next_bit implementation)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+#include <arch/arch.h>
+#include <error.h>
+#include <atomic.h>
+#include <string.h>
+#include <assert.h>
+#include <bitops.h>
+#include <bitmap.h>
+
+unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
+{
+       unsigned long words;
+       unsigned long tmp;
+
+       /* Start at final word. */
+       words = size / BITS_PER_LONG;
+
+       /* Partial final word? */
+       if (size & (BITS_PER_LONG-1)) {
+               tmp = (addr[words] & (~0UL >> (BITS_PER_LONG
+                                        - (size & (BITS_PER_LONG-1)))));
+               if (tmp)
+                       goto found;
+       }
+
+       while (words) {
+               tmp = addr[--words];
+               if (tmp) {
+found:
+                       return words * BITS_PER_LONG + __fls(tmp);
+               }
+       }
+
+       /* Not found */
+       return size;
+}
+
diff --git a/kern/src/find_next_bit.c b/kern/src/find_next_bit.c
new file mode 100644 (file)
index 0000000..8c8f4b6
--- /dev/null
@@ -0,0 +1,156 @@
+/* find_next_bit.c: fallback find next bit implementation
+ *
+ * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
+ * Written by David Howells (dhowells@redhat.com)
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version
+ * 2 of the License, or (at your option) any later version.
+ */
+
+#include <arch/arch.h>
+#include <error.h>
+#include <atomic.h>
+#include <string.h>
+#include <assert.h>
+#include <bitops.h>
+#include <bitmap.h>
+
+#define BITOP_WORD(nr)         ((nr) / BITS_PER_LONG)
+
+/*
+ * Find the next set bit in a memory region.
+ */
+unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
+                           unsigned long offset)
+{
+       const unsigned long *p = addr + BITOP_WORD(offset);
+       unsigned long result = offset & ~(BITS_PER_LONG-1);
+       unsigned long tmp;
+
+       if (offset >= size)
+               return size;
+       size -= result;
+       offset %= BITS_PER_LONG;
+       if (offset) {
+               tmp = *(p++);
+               tmp &= (~0UL << offset);
+               if (size < BITS_PER_LONG)
+                       goto found_first;
+               if (tmp)
+                       goto found_middle;
+               size -= BITS_PER_LONG;
+               result += BITS_PER_LONG;
+       }
+       while (size & ~(BITS_PER_LONG-1)) {
+               if ((tmp = *(p++)))
+                       goto found_middle;
+               result += BITS_PER_LONG;
+               size -= BITS_PER_LONG;
+       }
+       if (!size)
+               return result;
+       tmp = *p;
+
+found_first:
+       tmp &= (~0UL >> (BITS_PER_LONG - size));
+       if (tmp == 0UL)         /* Are any bits set? */
+               return result + size;   /* Nope. */
+found_middle:
+       return result + __ffs(tmp);
+}
+
+/*
+ * This implementation of find_{first,next}_zero_bit was stolen from
+ * Linus' asm-alpha/bitops.h.
+ */
+unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
+                                unsigned long offset)
+{
+       const unsigned long *p = addr + BITOP_WORD(offset);
+       unsigned long result = offset & ~(BITS_PER_LONG-1);
+       unsigned long tmp;
+
+       if (offset >= size)
+               return size;
+       size -= result;
+       offset %= BITS_PER_LONG;
+       if (offset) {
+               tmp = *(p++);
+               tmp |= ~0UL >> (BITS_PER_LONG - offset);
+               if (size < BITS_PER_LONG)
+                       goto found_first;
+               if (~tmp)
+                       goto found_middle;
+               size -= BITS_PER_LONG;
+               result += BITS_PER_LONG;
+       }
+       while (size & ~(BITS_PER_LONG-1)) {
+               if (~(tmp = *(p++)))
+                       goto found_middle;
+               result += BITS_PER_LONG;
+               size -= BITS_PER_LONG;
+       }
+       if (!size)
+               return result;
+       tmp = *p;
+
+found_first:
+       tmp |= ~0UL << size;
+       if (tmp == ~0UL)        /* Are any bits zero? */
+               return result + size;   /* Nope. */
+found_middle:
+       return result + ffz(tmp);
+}
+
+/*
+ * Find the first set bit in a memory region.
+ */
+unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
+{
+       const unsigned long *p = addr;
+       unsigned long result = 0;
+       unsigned long tmp;
+
+       while (size & ~(BITS_PER_LONG-1)) {
+               if ((tmp = *(p++)))
+                       goto found;
+               result += BITS_PER_LONG;
+               size -= BITS_PER_LONG;
+       }
+       if (!size)
+               return result;
+
+       tmp = (*p) & (~0UL >> (BITS_PER_LONG - size));
+       if (tmp == 0UL)         /* Are any bits set? */
+               return result + size;   /* Nope. */
+found:
+       return result + __ffs(tmp);
+}
+
+/*
+ * Find the first cleared bit in a memory region.
+ */
+unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
+{
+       const unsigned long *p = addr;
+       unsigned long result = 0;
+       unsigned long tmp;
+
+       while (size & ~(BITS_PER_LONG-1)) {
+               if (~(tmp = *(p++)))
+                       goto found;
+               result += BITS_PER_LONG;
+               size -= BITS_PER_LONG;
+       }
+       if (!size)
+               return result;
+
+       tmp = (*p) | (~0UL << size);
+       if (tmp == ~0UL)        /* Are any bits zero? */
+               return result + size;   /* Nope. */
+found:
+       return result + ffz(tmp);
+}
+