From bfd04df4807197261b9d36f16c5788a733129c05 Mon Sep 17 00:00:00 2001
From: Michael Sevakis <jethead71@rockbox.org>
Date: Wed, 18 Jan 2017 08:29:54 -0500
Subject: Dircache: Improve freed name memory recallocation

There's only a need to check every MAX_TINYNAME+1 bytes and that the
last character of the needed size 0xff in order to verify the size
of the block since the minimum indirectly-stored string is
MAX_TINYNAME+1.

Change-Id: Ic789376b8575bab9266fcd54c610db0961de5d7f
---
 firmware/common/dircache.c | 62 +++++++++++++++++++++++++++-------------------
 1 file changed, 36 insertions(+), 26 deletions(-)

diff --git a/firmware/common/dircache.c b/firmware/common/dircache.c
index e8f149cad0..0cdaf1bd4a 100644
--- a/firmware/common/dircache.c
+++ b/firmware/common/dircache.c
@@ -781,56 +781,66 @@ static int alloc_name(size_t size)
     if (dircache.namesfree >= size)
     {
         /* scan for a free gap starting at the hint point - first fit */
-        unsigned char *start = get_name(dircache.nextnamefree), *p = start;
-        unsigned char *namesend = get_name(dircache.names + dircache.sizenames);
-        size_t gapsize = 0;
+        unsigned char * const start = get_name(dircache.nextnamefree);
+        unsigned char * const bufend = get_name(dircache.names + dircache.sizenames);
+        unsigned char *p = start;
+        unsigned char *end = bufend;
 
-        while (gapsize < size)
+        while (1)
         {
-            if ((p = memchr(p, 0xff, namesend - p)))
+            if ((size_t)(bufend - p) >= size && (p = memchr(p, 0xff, end - p)))
             {
                 /* found a sentinel; see if there are enough in a row */
-                gapsize = 1;
-                while (*++p == 0xff && gapsize < size)
-                    gapsize++;
+                unsigned char *q = p + size - 1;
+
+                /* check end byte and every MAX_TINYNAME+1 bytes from the end;
+                   the minimum-length indirectly allocated string that could be
+                   in between must have at least one character at one of those
+                   locations */
+                while (q > p && *q == 0xff)
+                    q -= MAX_TINYNAME+1;
+
+                if (q <= p)
+                {
+                    nameidx = get_nameidx(p);
+                    break;
+                }
+
+                p += size;
             }
             else
             {
-                if (namesend == start)
+                if (end == start)
                     break; /* exhausted */
 
                 /* wrap */
-                namesend = start;
+                end = start;
                 p = get_name(dircache.names);
 
-                if (p == namesend)
+                if (p == end)
                     break; /* initial hint was at names start */
             }
         }
 
-        if (gapsize >= size)
+        if (nameidx)
         {
-            unsigned char *namep = p - gapsize;
-            nameidx = get_nameidx(namep);
-
-            if (*p == 0xff)
+            unsigned char *q = p + size;
+            if (q[0] == 0xff && q[MAX_TINYNAME] != 0xff)
             {
-                /* if only a tiny block remains after buffer, claim it too */
-                size_t tinysize = 1;
-                while (*++p == 0xff && tinysize <= MAX_TINYNAME)
-                    tinysize++;
-
-                if (tinysize <= MAX_TINYNAME)
+                /* if only a tiny block remains after buffer, claim it and
+                   hide it from scans since it's too small for indirect
+                   allocation */
+                do
                 {
-                    /* mark with tiny block sentinel */
-                    memset(p - tinysize, 0xfe, tinysize);
-                    size += tinysize;
+                    *q = 0xfe;
+                    size++;
                 }
+                while (*++q == 0xff);
             }
 
             dircache.namesfree -= size;
             dircache.sizeused += size;
-            set_namesfree_hint(namep + size);
+            set_namesfree_hint(p + size);
         }
     }
 
-- 
cgit