Make Pintos able to build with "gcc -m32" on x86-64 hosts without the
authorBen Pfaff <blp@cs.stanford.edu>
Thu, 5 Oct 2006 00:44:09 +0000 (00:44 +0000)
committerBen Pfaff <blp@cs.stanford.edu>
Thu, 5 Oct 2006 00:44:09 +0000 (00:44 +0000)
need for the host to have any 32-bit libraries (specifically, without
needing libgcc).

src/Make.config
src/Makefile.build
src/Makefile.userprog
src/lib/arithmetic.c [new file with mode: 0644]

index b1d480e70ae51453e636057e5b7d556722443825..91c14d00623696983a47483f970e55a590f9bea3 100644 (file)
@@ -6,16 +6,24 @@ VPATH = $(SRCDIR)
 
 # Binary utilities.
 # If the host appears to be x86, use the normal tools.
+# If it's x86-64, use the compiler and linker in 32-bit mode.
 # Otherwise assume cross-tools are installed as i386-elf-*.
 X86 = i.86\|pentium.*\|[pk][56]\|nexgen\|viac3\|6x86\|athlon.*
+X86_64 = x86_64
 ifneq (0, $(shell expr `uname -m` : '$(X86)'))
-CC = gcc
-LD = ld
-OBJCOPY = objcopy
+  CC = gcc
+  LD = ld
+  OBJCOPY = objcopy
 else
-CC = i386-elf-gcc
-LD = i386-elf-ld
-OBJCOPY = i386-elf-objcopy
+  ifneq (0, $(shell expr `uname -m` : '$(X86_64)'))
+    CC = gcc -m32
+    LD = ld -melf_i386
+    OBJCOPY = objcopy
+  else
+    CC = i386-elf-gcc
+    LD = i386-elf-ld
+    OBJCOPY = i386-elf-objcopy
+  endif
 endif
 
 ifeq ($(strip $(shell command -v $(CC) 2> /dev/null)),)
index 9a2728d356a1441bd4d13701022908a61b07870e..8a45c933d92aebbc1cd3c90dcd94357dddde67ab 100644 (file)
@@ -37,6 +37,7 @@ lib_SRC += lib/random.c                       # Pseudo-random numbers.
 lib_SRC += lib/stdio.c                 # I/O library.
 lib_SRC += lib/stdlib.c                        # Utility functions.
 lib_SRC += lib/string.c                        # String functions.
+lib_SRC += lib/arithmetic.c
 
 # Kernel-specific library code.
 lib/kernel_SRC  = lib/kernel/debug.c   # Debug helpers.
@@ -72,7 +73,7 @@ threads/kernel.lds.s: CPPFLAGS += -P
 threads/kernel.lds.s: threads/kernel.lds.S threads/loader.h
 
 kernel.o: threads/kernel.lds.s $(OBJECTS) 
-       $(LD) -T $< -o $@ $(OBJECTS) `$(CC) -print-libgcc-file-name`
+       $(LD) -T $< -o $@ $(OBJECTS)
 
 kernel.bin: kernel.o
        $(OBJCOPY) -O binary -R .note -R .comment -S $< $@.tmp
index 447088e8e7896212d8b5ce91879a0854b43f4cd4..3631cf1b221b2a3bf3e5e0fb02457338a39132db 100644 (file)
@@ -4,7 +4,6 @@ $(PROGS): CPPFLAGS += -I$(SRCDIR)/lib/user -I.
 
 # Linker flags.
 $(PROGS): LDFLAGS = -nostdlib -static -Wl,-T,$(LDSCRIPT)
-$(PROGS): LDLIBS = $(shell $(CC) -print-libgcc-file-name)
 $(PROGS): LDSCRIPT = $(SRCDIR)/lib/user/user.lds
 
 # Library code shared between kernel and user programs.
@@ -13,6 +12,7 @@ lib_SRC += lib/random.c                       # Pseudo-random numbers.
 lib_SRC += lib/stdio.c                 # I/O library.
 lib_SRC += lib/stdlib.c                        # Utility functions.
 lib_SRC += lib/string.c                        # String functions.
+lib_SRC += lib/arithmetic.c
 
 # User level only library code.
 lib/user_SRC  = lib/user/debug.c       # Debug helpers.
@@ -32,7 +32,7 @@ all: $(PROGS)
 define TEMPLATE
 $(1)_OBJ = $(patsubst %.c,%.o,$(patsubst %.S,%.o,$($(1)_SRC)))
 $(1): $$($(1)_OBJ) $$(LIB) $$(LDSCRIPT)
-       $$(CC) $$(LDFLAGS) $$($(1)_OBJ) $$(LIB) $$(LDLIBS) -o $$@
+       $$(CC) $$(LDFLAGS) $$($(1)_OBJ) $$(LIB) -o $$@
 endef
 
 $(foreach prog,$(PROGS),$(eval $(call TEMPLATE,$(prog))))
diff --git a/src/lib/arithmetic.c b/src/lib/arithmetic.c
new file mode 100644 (file)
index 0000000..bfc9b5a
--- /dev/null
@@ -0,0 +1,189 @@
+#include <stdint.h>
+
+/* On x86, division of one 64-bit integer by another cannot be
+   done with a single instruction or a short sequence.  Thus, GCC
+   implements 64-bit division and remainder operations through
+   function calls.  These functions are normally obtained from
+   libgcc, which is automatically included by GCC in any link
+   that it does.
+
+   Some x86-64 machines, however, have a compiler and utilities
+   that can generate 32-bit x86 code without having any of the
+   necessary libraries, including libgcc.  Thus, we can make
+   Pintos work on these machines by simply implementing our own
+   64-bit division routines, which are the only routines from
+   libgcc that Pintos requires.
+
+   Completeness is another reason to include these routines.  If
+   Pintos is completely self-contained, then that makes it that
+   much less mysterious. */
+
+/* Uses x86 DIVL instruction to divide 64-bit N by 32-bit D to
+   yield a 32-bit quotient.  Returns the quotient.
+   Traps with a divide error (#DE) if the quotient does not fit
+   in 32 bits. */
+static inline uint32_t
+divl (uint64_t n, uint32_t d)
+{
+  uint32_t n1 = n >> 32;
+  uint32_t n0 = n;
+  uint32_t q, r;
+
+  asm ("divl %4"
+       : "=d" (r), "=a" (q)
+       : "0" (n1), "1" (n0), "rm" (d));
+
+  return q;
+}
+
+/* Returns the number of leading zero bits in X,
+   which must be nonzero. */
+static int
+nlz (uint32_t x) 
+{
+  /* This technique is portable, but there are better ways to do
+     it on particular systems.  With sufficiently new enough GCC,
+     you can use __builtin_clz() to take advantage of GCC's
+     knowledge of how to do it.  Or you can use the x86 BSR
+     instruction directly. */
+  int n = 0;
+  if (x <= 0x0000FFFF)
+    {
+      n += 16;
+      x <<= 16; 
+    }
+  if (x <= 0x00FFFFFF)
+    {
+      n += 8;
+      x <<= 8; 
+    }
+  if (x <= 0x0FFFFFFF)
+    {
+      n += 4;
+      x <<= 4;
+    }
+  if (x <= 0x3FFFFFFF)
+    {
+      n += 2;
+      x <<= 2; 
+    }
+  if (x <= 0x7FFFFFFF)
+    n++;
+  return n;
+}
+
+/* Divides unsigned 64-bit N by unsigned 64-bit D and returns the
+   quotient. */
+static uint64_t
+udiv64 (uint64_t n, uint64_t d)
+{
+  if ((d >> 32) == 0) 
+    {
+      /* Proof of correctness:
+
+         Let n, d, b, n1, and n0 be defined as in this function.
+         Let [x] be the "floor" of x.  Let T = b[n1/d].  Assume d
+         nonzero.  Then:
+             [n/d] = [n/d] - T + T
+                   = [n/d - T] + T                         by (1) below
+                   = [(b*n1 + n0)/d - T] + T               by definition of n
+                   = [(b*n1 + n0)/d - dT/d] + T
+                   = [(b(n1 - d[n1/d]) + n0)/d] + T
+                   = [(b[n1 % d] + n0)/d] + T,             by definition of %
+         which is the expression calculated below.
+
+         (1) Note that for any real x, integer i: [x] + i = [x + i].
+
+         To prevent divl() from trapping, [(b[n1 % d] + n0)/d] must
+         be less than b.  Assume that [n1 % d] and n0 take their
+         respective maximum values of d - 1 and b - 1:
+                 [(b(d - 1) + (b - 1))/d] < b
+             <=> [(bd - 1)/d] < b
+             <=> [b - 1/d] < b
+         which is a tautology.
+
+         Therefore, this code is correct and will not trap. */
+      uint64_t b = 1ULL << 32;
+      uint32_t n1 = n >> 32;
+      uint32_t n0 = n; 
+      uint32_t d0 = d;
+
+      return divl (b * (n1 % d0) + n0, d0) + b * (n1 / d0); 
+    }
+  else 
+    {
+      /* Based on the algorithm and proof available from
+         http://www.hackersdelight.org/revisions.pdf. */
+      if (n < d)
+        return 0;
+      else 
+        {
+          uint32_t d1 = d >> 32;
+          int s = nlz (d1);
+          uint64_t q = divl (n >> 1, (d << s) >> 32) >> (31 - s);
+          return n - (q - 1) * d < d ? q - 1 : q; 
+        }
+    }
+}
+
+/* Divides unsigned 64-bit N by unsigned 64-bit D and returns the
+   remainder. */
+static uint32_t
+umod64 (uint64_t n, uint64_t d)
+{
+  return n - d * udiv64 (n, d);
+}
+
+/* Divides signed 64-bit N by signed 64-bit D and returns the
+   quotient. */
+static int64_t
+sdiv64 (int64_t n, int64_t d)
+{
+  uint64_t n_abs = n >= 0 ? (uint64_t) n : -(uint64_t) n;
+  uint64_t d_abs = d >= 0 ? (uint64_t) d : -(uint64_t) d;
+  uint64_t q_abs = udiv64 (n_abs, d_abs);
+  return (n < 0) == (d < 0) ? (int64_t) q_abs : -(int64_t) q_abs;
+}
+
+/* Divides signed 64-bit N by signed 64-bit D and returns the
+   remainder. */
+static int32_t
+smod64 (int64_t n, int64_t d)
+{
+  return n - d * sdiv64 (n, d);
+}
+\f
+/* These are the routines that GCC calls. */
+
+long long __divdi3 (long long n, long long d);
+long long __moddi3 (long long n, long long d);
+unsigned long long __udivdi3 (unsigned long long n, unsigned long long d);
+unsigned long long __umoddi3 (unsigned long long n, unsigned long long d);
+
+/* Signed 64-bit division. */
+long long
+__divdi3 (long long n, long long d) 
+{
+  return sdiv64 (n, d);
+}
+
+/* Signed 64-bit remainder. */
+long long
+__moddi3 (long long n, long long d) 
+{
+  return smod64 (n, d);
+}
+
+/* Unsigned 64-bit division. */
+unsigned long long
+__udivdi3 (unsigned long long n, unsigned long long d) 
+{
+  return udiv64 (n, d);
+}
+
+/* Unsigned 64-bit remainder. */
+unsigned long long
+__umoddi3 (unsigned long long n, unsigned long long d) 
+{
+  return umod64 (n, d);
+}