possible bugs

[ashinn]

possible bugs

[GoogleCodeExporter]

--- gc.c    Wed Dec 02 15:00:54 2009 -0800
+++ gc.c    Fri Dec 04 13:45:59 2009 -0800
@@ -83,7 +83,7 @@
   for ( ; h; h=h->next) {
     p = (sexp) (h->data + sexp_heap_align(sexp_sizeof(pair)));
     q = h->free_list;
-    end = (char*)h->data + h->size;
+    end = (char*)h->data + h->size;  /* Incorrect?  h->data was aligned... */
     while (((char*)p) < end) {
       /* find the preceding and succeeding free list pointers */
       for (r=q->next; r && ((char*)r<(char*)p); q=r, r=r->next)

Original comment by [email protected] on 4 Dec 2009 at 9:54

[GoogleCodeExporter]

The dummy_ctx should be freed, thanks for catching that.
It was a tiny one-time malloc, though, so not a problem in practice.

The comment is just a comment pointing out that the first free cell
is marked 0 but not actually 0 - the actual size isn't important and
may detract from understanding.  It so happens that in all configurations
sexp_sizeof(pair) is already aligned though.

sexp_sizeof(pair) is basically my unit of operation - all heap values
are aligned on that size boundaries, so I use it sometimes where, say,
sexp_heap_align(sizeof(struct sexp_free_list)) would be more accurate.
Since I'm still changing things rapidly I don't want to mess with anything
in the GC that isn't broken, so I'll leave the other lines as-is.  If
you can find GC bug definitely report it, but that's unlikely as any bug
in the GC will turn up *very* quickly and usually result in a segfault.

When I get to a general cleanup phase I'll document gc.c and decide
how best to write things, but if I do any optimizing before then the
whole file may change drastically.

Original comment by [email protected] on 5 Dec 2009 at 9:04

• Changed state: Fixed

[GoogleCodeExporter]

I think I can prove sexp_make_heap is broken:

sizeof(struct sexp_heap) == 16
offsetof(struct sexp_heap, data) == 12
sexp_heap_align(sexp_sizeof(pair)) == 16

size = 1024
sexp_make_heap(size)

sexp_heap h = (sexp_heap) malloc(sizeof(struct sexp_heap) + size)
h == 0x12345678  /* malloc can place it anywhere */
end_of_h = 0x12345678 + 16 + 1024 == 0x12345A88

h->data = (char*) sexp_heap_align((sexp_uint_t)&(h->data));
free = h->free_list = (sexp_free_list) h->data;
free == sexp_heap_align(0x12345678 + 12) == 0x12345690

next = (sexp_free_list) ((char*)free + sexp_heap_align(sexp_sizeof(pair)));
next == 0x12345690 + 16 == 0x123456A0

next->size = size - sexp_heap_align(sexp_sizeof(pair));
next->size == 1024 - 16 == 1008

next + next->size == 0x123456A0 + 1008 == 0x12345A90
BUT! end_of_h == 0x12345A88

Because next->size == 1008, an object could be allocated which goes all the way 
to
0x12345A90, but this is passed the end of the range malloc allocated!

Original comment by [email protected] on 5 Dec 2009 at 10:51

[GoogleCodeExporter]

The fix I've been working on is like:

/* A new heap segment looks like:

                     ---------------------------------------------
                     | sexp_heap.size = sexp_heap_align(size)
                     ---------------------------------------------
                     | sexp_heap.next = NULL
                     ---------------------------------------------
                     | sexp_heap.sexp_free_list.size = 0
                     ---------------------------------------------
                     | sexp_heap.sexp_free_list.next = pointer to ---
                     ---------------------------------------------  |
                       ... alignment, never used ...                |
    a    -  aligned  --------------------------------------------- <-
    l s  |           | sexp_free_list.size = sexp_heap_align(size)
    i i  |           ---------------------------------------------
    g z  |           | sexp_free_list.next = NULL
    n e  |           ---------------------------------------------
    e    |             ... free ...
    d    -  aligned  ---------------------------------------------
                       ... alignment, never used ...
                     ---------------------------------------------
 */

#define sexp_heap_data(heap)                                            \
  ((void*) sexp_heap_align((sexp_uint_t)                                \
                           ((char*)(heap) + sizeof(struct sexp_heap))))

sexp_heap sexp_make_heap (size_t size) {
  sexp_heap h;
  size_t msize;
  size = sexp_heap_align(size);
  /* + sexp_heap_align(1) is done so that sexp_heap_align(size) bytes are truly
     available, because sexp_heap_data(h) is aligned and so might be offset from
     the end of the header struct */
  msize = sizeof(struct sexp_heap) + sexp_heap_align(1) + size;
  h = (sexp_heap) malloc(msize);
  if (! h)
    errx(70, "out of memory allocating %zu byte heap, aborting\n", size);
  h->size = size;
  h->next = NULL;
  h->free_list.size = 0;  /* actually sizeof(struct sexp_free_list) */
  h->free_list.next = (sexp_free_list) sexp_heap_data(h);
  h->free_list.next->size = size;
  h->free_list.next->next = NULL;
  return h;
}

Original comment by [email protected] on 5 Dec 2009 at 10:58

[GoogleCodeExporter]

Since you still might make significant changes, I understand why you don't want 
to
spend time cleaning-up yet.  I'm just excited to hack Chibi :)

Original comment by [email protected] on 5 Dec 2009 at 11:04