Malloc og free

Jeg hapsede lidt ud af headeren...mangler stadig værdien af 'headerSize'. Er det sizeof(struct Node) ?

Mit testprogram er faktisk ikke så vildt. Det udfører en række tilfældige allokeringer, deallokeringer og reallokeringer og udskriver inden noget C kode, som ville gøre det samme. F.eks.:

 WRITE_LOG("    buffers[%d] = rlmalloc(%d);\n", IDX, size);
 WRITE_LOG("    memset(buffers[%d], 'A', %d);\n", IDX, size);
 buffers[IDX] = rlmalloc(size);
 memset(buffers[IDX], 'A', size);

Hvis programmet crasher, så udskrives en epilogue:

 void finish(int sig) {
      WRITE_LOG("    return 0;\n");
      WRITE_LOG("}\n");
      exit(1);
 }

Resultatet bliver koden til et program, som udfører de samme skridt, som førte til en SIGSEGV.

Bob bob...hvilket styresystem?

Du har to variable kaldet *available_physical_memory. Har du virkelig adgang til fysisk hukommelse?

I Linux fungerer malloc ved at kontrollere hukommelsen op til systemets break (brk()). Har malloc selv brug for mere hukommelse, så flyttes break. For store allokeringer bruges mmap.

Jeg ser intet sted, hvor du beder styresystemet om mere hukommelse (som f.eks. ved et kald til sbrk()/mmap(). Er det måske derfor? Man kan jo under normale omstændigheder ikke bare bruge løs af hele adresserummet uden at mappe den pågældende hukommelse.

True. Vi kører styresystemet på en virtuel maskine, hvor *available_physical_memory, kun referere til starten på et stort array.

Ok, så burde den del jo virke. Kan jeg få dig til at poste lidt mere kode?
Header og så'n, så jeg kan compile, og også gerne et test program. Jeg lavede selv en malloc/free implementering engang og brugte følgende program til at teste den:

 #include <stdlib.h>
 #include <time.h>
 #include <stdio.h>
 #include <string.h>
 #include <signal.h>
 #include "rlmalloc.h"
 
 #define MAX_ITERATIONS 1000
 #define BUFFERS 64
 #define MAX_MEM 1000000
 #define IDX ((idx + i) % BUFFERS)
 
 #define WRITE_LOG(...) if (verbose) fprintf(stdout, __VA_ARGS__)
 
 struct sigaction action;
 int verbose = 1;
 
 void finish(int sig) {
     WRITE_LOG("    return 0;\n");
     WRITE_LOG("}\n");
     exit(1);
 }
 
 int main(int argc, char const *argv[]) {
     void * buffers[BUFFERS];
     int idx, i, cmd, seed, iterations = 0;
     size_t size;
     seed = argc > 1 ? atoi(argv[1]) : time(NULL);
     srand(seed);
     memset(buffers, 0, sizeof(buffers));
     memset(&action, 0, sizeof(struct sigaction));
 
     action.sa_handler = finish;
     sigaction(SIGSEGV, &action, NULL);
 
     WRITE_LOG("#include \"rlmalloc.h\"\n");
     WRITE_LOG("#include <string.h>\n");
     WRITE_LOG("int main(int argc, char const *argv[]) {\n");
     WRITE_LOG("    void * buffers[%d];\n", BUFFERS);
     WRITE_LOG("    memset(buffers, 0, sizeof(buffers));\n");
     while (iterations++ < MAX_ITERATIONS) {
         cmd = rand() % 3;
         idx = rand() % BUFFERS;
         switch (cmd) {
             case 0: /* rlmalloc */
                 for (i = 0; i < BUFFERS; i++) {
                     if (buffers[IDX] == NULL) {
                         size = rand() % MAX_MEM;
                         WRITE_LOG("    buffers[%d] = rlmalloc(%d);\n", IDX, size);
                         WRITE_LOG("    memset(buffers[%d], 'A', %d);\n", IDX, size);
                         buffers[IDX] = rlmalloc(size);
                         memset(buffers[IDX], 'A', size);
                         break;
                     }
                 }
             break;
             case 1: /* rlfree */
                 for (i = 0; i < BUFFERS; i++) {
                     if (buffers[IDX] != NULL) {
                         WRITE_LOG("    rlfree(buffers[%d]);\n", IDX);
                         WRITE_LOG("    buffers[%d] = NULL;\n", IDX);
                         rlfree(buffers[IDX]);
                         buffers[IDX] = NULL;
                         break;
                     }
                 }
             break;
             case 2: /* rlrealloc */
                 for (i = 0; i < BUFFERS; i++) {
                     if (buffers[IDX] != NULL) {
                         size = rand() % MAX_MEM;
                         WRITE_LOG("    buffers[%d] = rlrealloc(buffers[%d], %d);\n", IDX, IDX, size);
                         WRITE_LOG("    memset(buffers[%d], 'A', %d);\n", IDX, size);
                         buffers[IDX] = rlrealloc(buffers[IDX], size);
                         memset(buffers[IDX], 'A', size);
                         break;
                     }
                 }
             break;
         }
     }
     for (i = 0; i < BUFFERS; i++) {
         if (buffers[i] != NULL) {
             WRITE_LOG("    rlfree(buffers[%d]);\n", i);
             WRITE_LOG("    buffers[%d] = NULL;\n", i);
             rlfree(buffers[i]);
             buffers[i] = NULL;
         }
     }
     WRITE_LOG("    return 0;\n");
     WRITE_LOG("}\n");
 
     return 0;
 }

Jeg kan så køre det i en løkke indtil det fejler og pipe dets output til en C fil. Når det fejler har jeg en testcase, som jeg kan debugge på. Noget i stil med:

$ count=0; while ./test > fail.c; do printf "\r%d" $count; count=$((count+1)); done

Det vil udskrive antallet af gennemkørsler af programmet. Når løkken stopper kan jeg bare compile "fail.c" og køre det i en debugger. Det fangede jeg en del fejl på, men nu finder det ikke flere.

wow, det ser rimelig vildt ud, og nok lidt over mit niveau.

min header fil ser sådan her ud

 /* Copyright (c) 1997-2014, FenixOS Developers
    All Rights Reserved.
 
    This file is subject to the terms and conditions defined in
    file 'LICENSE', which is part of this source code package.
  */
 
 /*! \file globals.h This file holds declarations of various global
     variables.
  */
 
 #ifndef GLOBALS_H
 #define GLOBALS_H
 
 # include <stdint.h>
 
 # include "instruction_wrappers.h"
 
 # include <sysdefines.h>
 
 struct Node
 {
     struct Node *theNextNode;
     uint64_t* endOfNode;
 };
 
 /*! Structure which stores a context. */
 struct AMD64_context
 {
  /* The following fields must be the first in the struct. The order of
     fields must not change or the assembly code will break. */
  uint8_t  fp_context[512] __attribute__((aligned (16))); // offset 0x0
  uint64_t rax;             // offset 0x200
  uint64_t rbx;             // offset 0x208
  uint64_t rcx;             // offset 0x210
  uint64_t rdx;             // offset 0x218
  uint64_t rdi;             // offset 0x220
  uint64_t rsi;             // offset 0x228
  uint64_t rbp;             // offset 0x230
  uint64_t rsp;             // offset 0x238
  uint64_t r8;              // offset 0x240
  uint64_t r9;              // offset 0x248
  uint64_t r10;             // offset 0x250
  uint64_t r11;             // offset 0x258
  uint64_t r12;             // offset 0x260
  uint64_t r13;             // offset 0x268
  uint64_t r14;             // offset 0x270
  uint64_t r15;             // offset 0x278
  uint64_t rip;             // offset 0x280 - first instruction
  uint64_t rflags;          // offset 0x288 - set to 0x200 when calling process
  /* Additional fields can be added below */
  int      interrupt_context; /*!< True, i.e., not zero, iff the context is 
                                   saved in a interrupt handler. */
 };
 
 /*! Each processor has its own structure of this type. It is used
     to store data which is private to each cpu. */
 struct AMD64_kernel_GS_data
 {
  /* Warning: Do not change or add members to this struct. It would break
     the assembly code. */
 
  /*! The currently executing context. */
  struct AMD64_context * volatile active_context;   /* offset 0 */
 
  /*! Scratchpad variable used by the context switch routines. */
  uint64_t                       scratch_pad1;      /* offset 8 */
 
  /*! The stack used in system call handlers. */
  uint64_t                       syscall_stack;     /* offset 16 */
 };
 
 /* ELF image structures. The names from the ELF64 specification are used
    and the structs are derived from the ELF64 specification. */
 
 # define EI_MAG0       0  /*!< The first four bytes in an ELF image is
                                 0x7f 'E' 'L' 'F'. */
 # define EI_MAG1       1
 # define EI_MAG2       2
 # define EI_MAG3       3
 # define EI_CLASS      4  /*!< The specific ELF image class. */
 # define EI_DATA       5  /*!< Describes if the image is big- or little-
                                endian. */
 # define EI_VERSION    6  /*!< The version of the ELF specification the
                                image adheres to. */
 # define EI_OSABI      7  /*!< Type of OS the image can be run on. */
 # define EI_ABIVERSION 8  /*!< Version of the ABI used. */
 # define EI_PAD        9  /*!< First unused byte in the identification
                                array. */
 # define EI_NIDENT     16 /*!< Number of entries in the identification
                                array */
 
 /*! Defines an ELF64 file header. */
 struct Elf64_Ehdr
 {
  uint8_t  e_ident[EI_NIDENT]; /*!< Array of bytes that shows that
                                         this is an ELF image and what type
                                         of ELF image it is. */
  uint16_t e_type;             /*!< The type of ELF executable image. */
  uint16_t e_machine;          /*!< Identifies the type of machine
                                    that the image can execute on. */
  uint32_t e_version;          /*!< The version of the ELF
                                    specification the image adheres to. */
  uint64_t e_entry;            /*!< Start address of the executable. */
  uint64_t e_phoff;            /*!< The offset into the image where
                                    the program header table is
                                    found. */
  uint64_t e_shoff;            /*!< The offset into the image where
                                    the program header table is
                                    found. */
  uint32_t e_flags;            /*!< Flags that are machine specific.
                                    These can be used to differentiate
                                    between similar machines. */
  uint16_t e_ehsize;           /*!< The size, in bytes, of the header. */
  uint16_t e_phentsize;        /*!< The size, in bytes, of each entry
                                    in the program header table. */
  uint16_t e_phnum;            /*!< The size, in entries, of the
                                    program header table. */
  uint16_t e_shentsize;        /*!< The size, in bytes, of each entry
                                    in the section header table. */
  uint16_t e_shnum;            /*!< The size, in entries, of the
                                    section header table. */
  uint16_t e_shstrndx;         /*!< The index, into the section table,
                                    of the section name string table.*/
 };
 
 /*! Defines an entry in the ELF program header table. Each entry
     corresponds to a segment. */
 struct Elf64_Phdr
 {
  uint32_t p_type;   /*!< Segments can have several types. p_type holds the
                          type. */
  uint32_t p_flags;  /*!< The attribute flags of the segment. */
  uint64_t p_offset; /*!< Offset into the image of the first byte of the
                          segment */
  uint64_t p_vaddr;  /*!< The (virtual) address to which the segment is to
                          be loaded. */
  uint64_t p_paddr;  /*!< Not used. */
  uint64_t p_filesz; /*!< The number of bytes the segment occupies in the
                          image. */
  uint64_t p_memsz;  /*!< The number of bytes the segment occupies in
                          memory. */
  uint64_t p_align;  /*!< The alignment the segment should have in memory.
                          This field is currently being ignored. */
 };
 
 /* Values used in p_type */
 # define PT_NULL 0 /*!< The entry is not used. */
 # define PT_LOAD 1 /*!< The segment can be loaded into memory. */
 # define PT_PHDR 6 /*!< The segment only hold a program header table. */
 /* Values used in p_flags */
 # define PF_X        0x1        /*!< Segment can be executed.*/
 # define PF_W        0x2        /*!< Segment can be written. */
 # define PF_R        0x4        /*!< Segment can be read. */
 # define PF_MASKPERM 0x0000FFFF /*!< Used to mask the permission bits */
 
 /*! Copies an ELF image to memory. Does some checks to avoid that corrupt
     images gets copied to memory.
     \return The address to the first instruction to execute. */
 extern unsigned long
 copy_ELF(const struct Elf64_Ehdr* const elf_image
          /*!< Points to the ELF image to copy. */);
 
 /*! Returns the currently active context. */
 inline struct AMD64_context *
 get_active_context(void)
 {
  register struct AMD64_context * context;
  __asm volatile("mov %%gs:0,%0" : "=r" (context) : : );
  return context;
 }
 
 /*! Sets the currently active context. */
 inline void
 set_active_context(struct AMD64_context * const context /*!< the new context. */)
 {
  __asm volatile("mov %0,%%gs:0" : : "r" (context) : );
 }
 
 /*! Performs a context switch and go to user mode. Will return to caller if 
     the context is not valid. */
 inline void
 go_to_user_mode(void)
 {
  /* This is somewhat of a hack. This code will perform a decent context
     switch but more state should be switched. There are also performance
     optimizations to be made. */
  struct AMD64_context * const context = get_active_context();
 
  if (0 == context)
  {
   /* No proper context. */
   return;
  }
 
  /* Set FPU/MMX/SSE context. */
  fxrstor(context->fp_context);
 
  /* swap the gs. */
  __asm volatile("swapgs" :::);
 
  if (context->interrupt_context)
  {
 
      //%rax is system call id
      //%rdi index of ELF-image
   /* Set registers and return via iretq */
   __asm volatile("movq    0x200(%%rcx),%%rax \n \
                   movq    0x208(%%rcx),%%rbx \n \
                   movq    0x220(%%rcx),%%rdi \n \
                   movq    0x228(%%rcx),%%rsi \n \
                   movq    0x230(%%rcx),%%rbp \n \
                   movq    0x240(%%rcx),%%r8 \n \
                   movq    0x248(%%rcx),%%r9 \n \
                   movq    0x250(%%rcx),%%r10 \n \
                   movq    0x258(%%rcx),%%r11 \n \
                   movq    0x260(%%rcx),%%r12 \n \
                   movq    0x268(%%rcx),%%r13 \n \
                   movq    0x270(%%rcx),%%r14 \n \
                   movq    0x278(%%rcx),%%r15 \n \
                   movq    $11,%%rdx \n \
                   pushq   %%rdx \n \
                   pushq   0x238(%%rcx) \n \
                   pushq   0x288(%%rcx) \n \
                   pushq   $19 \n \
                   pushq   0x280(%%rcx) \n \
                   pushq   0x210(%%rcx) \n \
                   pushq   0x218(%%rcx) \n \
                   mov     %%dx,%%gs \n \
                   mov     %%dx,%%fs \n \
                   mov     %%dx,%%es \n \
                   mov     %%dx,%%ds \n \
                   popq    %%rdx \n \
                   popq    %%rcx \n \
                   iretq"
                  :
                  : "c"(context)
                  : "memory");
  }
  else
  {
   /* Set registers and return via sysret */
   __asm volatile("movq    0x200(%%rcx),%%rax \n \
                   movq    0x208(%%rcx),%%rbx \n \
                   movq    0x218(%%rcx),%%rdx \n \
                   movq    0x220(%%rcx),%%rdi \n \
                   movq    0x228(%%rcx),%%rsi \n \
                   movq    0x230(%%rcx),%%rbp \n \
                   movq    0x240(%%rcx),%%r8 \n \
                   movq    0x248(%%rcx),%%r9 \n \
                   movq    0x250(%%rcx),%%r10 \n \
                   movq    0x260(%%rcx),%%r12 \n \
                   movq    0x268(%%rcx),%%r13 \n \
                   movq    0x270(%%rcx),%%r14 \n \
                   movq    0x278(%%rcx),%%r15 \n \
                   movq    0x288(%%rcx),%%r11 \n \
                   pushq   0x238(%%rcx) \n \
                   pushq   0x280(%%rcx) \n \
                   mov     $11,%%ecx \n \
                   mov     %%cx,%%gs \n \
                   mov     %%cx,%%fs \n \
                   mov     %%cx,%%es \n \
                   mov     %%cx,%%ds \n \
                   popq    %%rcx \n \
                   popq    %%rsp \n \
                   sysretq"
                  :
                  : "c"(context)
                  : "memory");
  }
 }
 
 extern void
 amd64_syscall_entry_point(void) __attribute__ ((noreturn));
 
 extern void
 amd64_syscall_dummy_target(void) __attribute__ ((noreturn));
 
 extern void
 amd64_enter_kernel(void) __attribute__ ((noreturn));
 
 extern void
 amd64_handle_interrupt_user(int interrupt) __attribute__ ((noreturn));
 
 extern void
 amd64_handle_interrupt_super(int interrupt);
 
 extern void
 amd64_handle_exception_user(int exc) __attribute__ ((noreturn));
 
 extern void
 amd64_handle_exception_super(int exc);
 
 extern void
 amd64_handle_exception_w_error_user(int exc,
                                     uint32_t code) __attribute__ ((noreturn));
 
 extern void
 amd64_handle_exception_w_error_super(int exc, uint32_t code);
 
 extern void
 amd64_handle_nmi_user(int dummy) __attribute__ ((noreturn));
 
 extern void
 amd64_handle_nmi_super(int dummy);
 
 extern const struct Elf64_Ehdr* const 
 ELF_images[1];
 /*!< Array of pointers to ELF images. The array ends with a null
      pointer. The array itself is created by the linker and no
      definition is visible in the source code. */
 
 /*! Assembly routine which will halt the calling processor forever. */
 extern void
 amd64_halt(void)  __attribute__ ((noreturn));
 
 /*! Assembly routine which will cause the calling processor to envoke
     the Bochs debugger. */
 extern void
 amd64_enter_debugger(void);
 
 
 /*! Allocates a memory block.
     \return an address to the memory block or an error code if
             the allocation was not successful. */
 extern long
 kalloc(const register uint64_t length
        /*!< The number of bytes to allocate. */);
 
 /*! Frees a previously allocated a memory block.
     \return ALL_OK if successful or an error code if
             the free was not successful. */
 extern long
 kfree(const register uint64_t address
        /*!< The address to the memory block to free. */);
 
 /*! Outputs a string through the terminal emulator. */
 extern void
 kprints(const char* const string
         /*!< Points to a null terminated string */);
 
 /*! Outputs an unsigned 64-bit value through the terminal emulator. */
 extern void
 kprinthex(const register uint64_t value /*! value to be printed. */);
 
 extern uint64_t allign32( const register uint64_t length);
 
 #endif

og er en del at det større system, så det er ikke sikker det giver mening.

Mvh

I see. Det var faktisk en opgave vi havde tidligere på semesteret, og der virkede mine funktioner. Der var et testprogram, som allokerede og free'ede nogle tilfældige størrelse.

i den nye udgave, som jeg satte ind tidligere, er headersize:

 const uint64_t headerSize = 32 / sizeof(uint64_t);

I den tidligere version, hvor det virkede, havde jeg dog mulighed for at bruge int istedet for uint64_t.

Mvh

Hmm...så headerSize bliver mindre (halvt så stor), når du går fra 32 til 64 bit. Kan det være rigtigt?
Jeg ville have forventet en fordobling.

Det er et krav i opgaven, at memory blokke bliver "aligned on a 32 byte basis".

Men jeg kan se, at headerSize bruges til mere end bare alignment...f.eks. denne:

        allocationStart = (uint64_t*) incomingBlock + headerSize;
....
    return (uint64_t) allocationStart;

På en 32 bit maskine bliver det til:

        allocationStart = (uint32_t*) incomingBlock + 8;

..og på en 64 bit maskine er det:

        allocationStart = (uint64_t*) incomingBlock + 4;

Hvis der er en header i starten af blokken, og du vil springe over den, så giver det jo ikke mening at headeren bliver mindre, når pointerne bliver større.

I styresystemet, bliver 64_bit kernel portet til 32 bit kernel. Vi har også fået nogle test-programmer som kalder hinanden og blot udskriver noget på skærmen. Hvis jeg hardcoder
allocationStart = *available_physical_memory, kan den køre første program, men da den så kalder næste crasher alt.
:/