Changeset da68871a in mainline for uspace/lib/c/generic

Timestamp:

2012-08-08T08:46:22Z (13 years ago)

Author:

Adam Hraska <adam.hraska+hos@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

30c0826

Parents:

bc216a0 (diff), 1d01cca (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merged changes from mainline.

Location:

uspace/lib/c/generic

Files:

• device/ahci.c (added)
• malloc.c (modified) (9 diffs)
• str.c (modified) (5 diffs)

uspace/lib/c/generic/malloc.c

@@ -109 +109 @@
         (((uintptr_t) (area)->end) - sizeof(heap_block_foot_t))
 
+#define AREA_LAST_BLOCK_HEAD(area) \
+        ((uintptr_t) BLOCK_HEAD(((heap_block_foot_t *) AREA_LAST_BLOCK_FOOT(area))))
+
 /** Get header in heap block.
  *
@@ -346 +349 @@
                 return false;
         
-        /* Add new free block */
-        size_t net_size = (size_t) (end - area->end);
-        if (net_size > 0)
-                block_init(area->end, net_size, true, area);
+        heap_block_head_t *last_head =
+            (heap_block_head_t *) AREA_LAST_BLOCK_HEAD(area);
+        
+        if (last_head->free) {
+                /* Add the new space to the last block. */
+                size_t net_size = (size_t) (end - area->end) + last_head->size;
+                malloc_assert(net_size > 0);
+                block_init(last_head, net_size, true, area);
+        } else {
+                /* Add new free block */
+                size_t net_size = (size_t) (end - area->end);
+                if (net_size > 0)
+                        block_init(area->end, net_size, true, area);
+        }
         
         /* Update heap area parameters */
@@ -355 +368 @@
         
         return true;
-}
-
-/** Try to enlarge any of the heap areas
- *
- * Should be called only inside the critical section.
- *
- * @param size Gross size of item to allocate (bytes).
- *
- */
-static bool heap_grow(size_t size)
-{
-        if (size == 0)
-                return true;
-        
-        /* First try to enlarge some existing area */
-        for (heap_area_t *area = first_heap_area; area != NULL;
-            area = area->next) {
-                if (area_grow(area, size))
-                        return true;
-        }
-        
-        /* Eventually try to create a new area */
-        return area_create(AREA_OVERHEAD(size));
 }
 
@@ -661 +651 @@
 }
 
+/** Try to enlarge any of the heap areas.
+ *
+ * If successful, allocate block of the given size in the area.
+ * Should be called only inside the critical section.
+ *
+ * @param size  Gross size of item to allocate (bytes).
+ * @param align Memory address alignment.
+ *
+ * @return Allocated block.
+ * @return NULL on failure.
+ *
+ */
+static void *heap_grow_and_alloc(size_t size, size_t align)
+{
+        if (size == 0)
+                return NULL;
+        
+        /* First try to enlarge some existing area */
+        for (heap_area_t *area = first_heap_area; area != NULL;
+            area = area->next) {
+                
+                if (area_grow(area, size + align)) {
+                        heap_block_head_t *first =
+                            (heap_block_head_t *) AREA_LAST_BLOCK_HEAD(area);
+                        
+                        void *addr =
+                            malloc_area(area, first, NULL, size, align);
+                        malloc_assert(addr != NULL);
+                        return addr;
+                }
+        }
+        
+        /* Eventually try to create a new area */
+        if (area_create(AREA_OVERHEAD(size + align))) {
+                heap_block_head_t *first =
+                    (heap_block_head_t *) AREA_FIRST_BLOCK_HEAD(last_heap_area);
+                
+                void *addr =
+                    malloc_area(last_heap_area, first, NULL, size, align);
+                malloc_assert(addr != NULL);
+                return addr;
+        }
+        
+        return NULL;
+}
+
 /** Allocate a memory block
  *
@@ -679 +715 @@
         
         size_t falign = lcm(align, BASE_ALIGN);
-        size_t real_size = GROSS_SIZE(ALIGN_UP(size, falign));
-        
-        bool retry = false;
-        heap_block_head_t *split;
-        
-loop:
+        
+        /* Check for integer overflow. */
+        if (falign < align)
+                return NULL;
+        
+        /*
+         * The size of the allocated block needs to be naturally
+         * aligned, because the footer structure also needs to reside
+         * on a naturally aligned address in order to avoid unaligned
+         * memory accesses.
+         */
+        size_t gross_size = GROSS_SIZE(ALIGN_UP(size, BASE_ALIGN));
         
         /* Try the next fit approach */
-        split = next_fit;
+        heap_block_head_t *split = next_fit;
         
         if (split != NULL) {
-                void *addr = malloc_area(split->area, split, NULL, real_size,
+                void *addr = malloc_area(split->area, split, NULL, gross_size,
                     falign);
                 
@@ -703 +745 @@
                     AREA_FIRST_BLOCK_HEAD(area);
                 
-                void *addr = malloc_area(area, first, split, real_size,
+                void *addr = malloc_area(area, first, split, gross_size,
                     falign);
                 
@@ -710 +752 @@
         }
         
-        if (!retry) {
-                /* Try to grow the heap space */
-                if (heap_grow(real_size)) {
-                        retry = true;
-                        goto loop;
-                }
-        }
-        
-        return NULL;
+        /* Finally, try to grow heap space and allocate in the new area. */
+        return heap_grow_and_alloc(gross_size, falign);
 }
 
@@ -731 +766 @@
 void *calloc(const size_t nmemb, const size_t size)
 {
+        // FIXME: Check for overflow
+        
         void *block = malloc(nmemb * size);
         if (block == NULL)
@@ -870 +907 @@
         if (addr == NULL)
                 return;
-
+        
         futex_down(&malloc_futex);
         

uspace/lib/c/generic/str.c

@@ -428 +428 @@
  *
  * Do a char-by-char comparison of two NULL-terminated strings.
- * The strings are considered equal iff they consist of the same
- * characters on the minimum of their lengths.
+ * The strings are considered equal iff their length is equal
+ * and both strings consist of the same sequence of characters.
+ *
+ * A string S1 is less than another string S2 if it has a character with
+ * lower value at the first character position where the strings differ.
+ * If the strings differ in length, the shorter one is treated as if
+ * padded by characters with a value of zero.
  *
  * @param s1 First string to compare.
  * @param s2 Second string to compare.
  *
- * @return 0 if the strings are equal, -1 if first is smaller,
- *         1 if second smaller.
+ * @return 0 if the strings are equal, -1 if the first is less than the second,
+ *         1 if the second is less than the first.
  *
  */
@@ -466 +471 @@
  *
  * Do a char-by-char comparison of two NULL-terminated strings.
- * The strings are considered equal iff they consist of the same
- * characters on the minimum of their lengths and the length limit.
+ * The strings are considered equal iff
+ * min(str_length(s1), max_len) == min(str_length(s2), max_len)
+ * and both strings consist of the same sequence of characters,
+ * up to max_len characters.
+ *
+ * A string S1 is less than another string S2 if it has a character with
+ * lower value at the first character position where the strings differ.
+ * If the strings differ in length, the shorter one is treated as if
+ * padded by characters with a value of zero. Only the first max_len
+ * characters are considered.
  *
  * @param s1      First string to compare.
@@ -473 +486 @@
  * @param max_len Maximum number of characters to consider.
  *
- * @return 0 if the strings are equal, -1 if first is smaller,
- *         1 if second smaller.
+ * @return 0 if the strings are equal, -1 if the first is less than the second,
+ *         1 if the second is less than the first.
  *
  */
@@ -508 +521 @@
         return 0;
 
+}
+
+/** Test whether p is a prefix of s.
+ *
+ * Do a char-by-char comparison of two NULL-terminated strings
+ * and determine if p is a prefix of s.
+ *
+ * @param s The string in which to look
+ * @param p The string to check if it is a prefix of s
+ *
+ * @return true iff p is prefix of s else false
+ *
+ */
+bool str_test_prefix(const char *s, const char *p)
+{
+        wchar_t c1 = 0;
+        wchar_t c2 = 0;
+        
+        size_t off1 = 0;
+        size_t off2 = 0;
+
+        while (true) {
+                c1 = str_decode(s, &off1, STR_NO_LIMIT);
+                c2 = str_decode(p, &off2, STR_NO_LIMIT);
+                
+                if (c2 == 0)
+                        return true;
+
+                if (c1 != c2)
+                        return false;
+                
+                if (c1 == 0)
+                        break;
+        }
+
+        return false;
 }
 
@@ -1085 +1134 @@
                 c = (c >= 'a' ? c - 'a' + 10 : (c >= 'A' ? c - 'A' + 10 :
                     (c <= '9' ? c - '0' : 0xff)));
-                if (c > base) {
+                if (c >= base) {
                         break;
                 }