Changeset 3457 for trunk/src/kash/memalloc.c

Timestamp:

Sep 14, 2020, 7:34:28 PM (5 years ago)

Author:

bird

Message:

kash: New parser allocator for non-forked-mode.

File:

• trunk/src/kash/memalloc.c (modified) (9 diffs)

trunk/src/kash/memalloc.c

@@ -42 +42 @@
 
 #include <stdlib.h>
+#include <stddef.h>
 #include <assert.h>
 
@@ -183 +184 @@
         mark->stacknleft = psh->stacknleft;
         mark->marknext = psh->markp;
+#ifdef KASH_SEPARATE_PARSER_ALLOCATOR
+        mark->pstacksize = psh->pstacksize;
+#endif
         psh->markp = mark;
 }
@@ -201 +205 @@
         psh->stacknxt = mark->stacknxt;
         psh->stacknleft = mark->stacknleft;
+
+#ifdef KASH_SEPARATE_PARSER_ALLOCATOR
+        assert(mark->pstacksize <= psh->pstacksize);
+        while (mark->pstacksize < psh->pstacksize) {
+                unsigned idx = --psh->pstacksize;
+                pstack_block *psk = psh->pstack[idx];
+                psh->pstack[idx] = NULL;
+                if (psh->curpstack == psk)
+                    psh->curpstack = idx > 0 ? psh->pstack[idx - 1] : NULL;
+                pstackrelease(psh, psk);
+        }
+
+# ifndef NDEBUG
+        if (psh->curpstack) {
+                unsigned i;
+                for (i = 0; i < psh->pstacksize; i++)
+                        if (psh->curpstack == psh->pstack[i])
+                                break;
+                assert(i < psh->pstacksize);
+        }
+# endif
+#endif
         INTON;
 }
@@ -354 +380 @@
  * Parser stack allocator.
  */
+#ifdef KASH_SEPARATE_PARSER_ALLOCATOR
+
+unsigned pstackretain(pstack_block *pst)
+{
+        unsigned refs = sh_atomic_inc(&pst->refs);
+        assert(refs > 1);
+        assert(refs < 256 /* bogus, but useful */);
+        return refs;
+}
+
+unsigned pstackrelease(shinstance *psh, pstack_block *pst)
+{
+        unsigned refs;
+        if (pst) {
+                refs = sh_atomic_dec(&pst->refs);
+                if (refs == 0) {
+                        shinstance * const psh = shthread_get_shell();
+                        struct stack_block *top;
+                        while ((top = pst->top) != &pst->first)
+                        {
+                            pst->top = top->prev;
+                            assert(pst->top);
+                            top->prev = NULL;
+                            sh_free(psh, top);
+                        }
+                        pst->nextbyte = NULL;
+                        pst->top = NULL;
+                        sh_free(psh, pst);
+                }
+        } else
+                refs = 0;
+        return refs;
+}
+
+pstack_block *pstackpush(shinstance *psh)
+{
+        size_t const blocksize = offsetof(pstack_block, first.space) + MINSIZE;
+        pstack_block *pst;
+        unsigned i;
+
+        INTOFF;
+
+        /*
+         * Allocate and initialize it.
+         */
+        pst = (pstack_block *)ckmalloc(psh, blocksize);
+        pst->nextbyte          = &pst->first.space[0];
+        pst->avail             = blocksize - offsetof(pstack_block, first.space);
+        pst->topsize           = blocksize - offsetof(pstack_block, first.space);
+        pst->strleft           = 0;
+        pst->top               = &pst->first;
+        pst->allocations       = 0;
+        pst->bytesalloced      = 0;
+        pst->nodesalloced      = 0;
+        pst->entriesalloced    = 0;
+        pst->strbytesalloced   = 0;
+        pst->blocks            = 0;
+        pst->fragmentation     = 0;
+        pst->refs              = 1;
+        pst->padding           = 42;
+        pst->first.prev        = NULL;
+
+        /*
+         * Push it onto the stack.
+         */
+        i = psh->pstacksize;
+        if (i + 1 < psh->pstackalloced) {
+                /* likely, except for the first time */
+        } else {
+                psh->pstack = (pstack_block **)ckrealloc(psh, psh->pstack, sizeof(psh->pstack[0]) * (i + 32));
+                memset(&psh->pstack[i], 0, sizeof(psh->pstack[0]) * 32);
+        }
+        psh->pstack[i] = pst;
+        psh->pstacksize = i + 1;
+        psh->curpstack = pst;
+
+        INTON;
+        return pst;
+}
+
+/**
+ * Allocates and pushes a new block onto the stack, min payload size @a nbytes.
+ */
+static void pstallocnewblock(shinstance *psh, pstack_block *pst, size_t nbytes)
+{
+        /* Allocate a new stack node. */
+        struct stack_block *sp;
+        size_t const blocksize = nbytes <= MINSIZE
+                               ? offsetof(struct stack_block, space) + MINSIZE
+                               : K_ALIGN_Z(nbytes + offsetof(struct stack_block, space), 1024);
+
+        INTOFF;
+        sp = ckmalloc(psh, blocksize);
+        sp->prev = pst->top;
+        pst->fragmentation += pst->avail;
+        pst->topsize        = blocksize - offsetof(struct stack_block, space);
+        pst->avail          = blocksize - offsetof(struct stack_block, space);
+        pst->nextbyte       = sp->space;
+        pst->top            = sp;
+        pst->blocks        += 1;
+        INTON;
+}
+
+/**
+ * Tries to grow the current stack block to hold a minimum of @a nbytes,
+ * will allocate a new block and copy over pending string bytes if that's not
+ * possible.
+ */
+static void pstgrowblock(shinstance *psh, pstack_block *pst, size_t nbytes, size_t tocopy)
+{
+        struct stack_block *top = pst->top;
+        size_t blocksize;
+
+        assert(pst->avail < nbytes); /* only called when we need more space */
+        assert(tocopy <= pst->avail);
+
+        /* Double the size used thus far and add some fudge and alignment.  Make
+           sure to at least allocate MINSIZE. */
+        blocksize = K_MAX(K_ALIGN_Z(pst->avail * 2 + 100 + offsetof(struct stack_block, space), 64), MINSIZE);
+
+        /* If that isn't sufficient, do request size w/ some fudge and alignment. */
+        if (blocksize < nbytes + offsetof(struct stack_block, space))
+            blocksize = K_ALIGN_Z(nbytes + offsetof(struct stack_block, space) + 100, 1024);
+
+        /*
+         * Reallocate the current stack node if we can.
+         */
+        if (   pst->nextbyte == &top->space[0] /* can't have anything else in the block */
+            && top->prev != NULL /* first block is embedded in pst and cannot be reallocated */ ) {
+                top = (struct stack_block *)ckrealloc(psh, top, blocksize);
+                pst->top      = top;
+                pst->topsize  = blocksize - offsetof(struct stack_block, space);
+                pst->avail    = blocksize - offsetof(struct stack_block, space);
+                pst->nextbyte = top->space;
+        }
+        /*
+         * Otherwise allocate a new node and copy over the avail bytes
+         * from the old one.
+         */
+        else {
+                char const * const copysrc = pst->nextbyte;
+                pstallocnewblock(psh, pst, nbytes);
+                assert(pst->avail >= nbytes);
+                assert(pst->avail >= tocopy);
+                memcpy(pst->nextbyte, copysrc, tocopy);
+        }
+}
+
+K_INLINE void *pstallocint(shinstance *psh, pstack_block *pst, size_t nbytes)
+{
+        void *ret;
+
+        /*
+         * Align the size and make sure we've got sufficient bytes available:
+         */
+        nbytes = SHELL_ALIGN(nbytes);
+        if (pst->avail >= nbytes && (ssize_t)pst->avail >= 0) { /* likely*/ }
+        else pstallocnewblock(psh, pst, nbytes);
+
+        /*
+         * Carve out the return block.
+         */
+        ret = pst->nextbyte;
+        pst->nextbyte     += nbytes;
+        pst->avail        -= nbytes;
+        pst->bytesalloced += nbytes;
+        pst->allocations  += 1;
+        return ret;
+}
+
+#endif KASH_SEPARATE_PARSER_ALLOCATOR
+
+
 void *pstalloc(struct shinstance *psh, size_t nbytes)
 {
+#ifdef KASH_SEPARATE_PARSER_ALLOCATOR
+        return pstallocint(psh, psh->curpstack, nbytes);
+#else
         return stalloc(psh, nbytes);
+#endif
 }
 
 union node *pstallocnode(struct shinstance *psh, size_t nbytes)
 {
+#ifdef KASH_SEPARATE_PARSER_ALLOCATOR
+        pstack_block *pst = psh->curpstack;
+        pst->nodesalloced++;
+        return (union node *)pstallocint(psh, pst, nbytes);
+#else
         return (union node *)pstalloc(psh, nbytes);
+#endif
 }
 
 struct nodelist *pstalloclist(struct shinstance *psh)
 {
+#ifdef KASH_SEPARATE_PARSER_ALLOCATOR
+        pstack_block *pst = psh->curpstack;
+        pst->entriesalloced++;
+        return (struct nodelist *)pstallocint(psh, pst, sizeof(struct nodelist));
+#endif
         return (struct nodelist *)pstalloc(psh, sizeof(struct nodelist));
 }
@@ -372 +586 @@
 {
         if (str) {
-                size_t nbytes = strlen(str) + 1;
+                size_t const nbytes = strlen(str) + 1;
+#ifdef KASH_SEPARATE_PARSER_ALLOCATOR
+                pstack_block *pst = psh->curpstack;
+                pst->strbytesalloced += SHELL_ALIGN(nbytes);
+                return (char *)memcpy(pstallocint(psh, pst, nbytes), str, nbytes);
+#else
                 return (char *)memcpy(pstalloc(psh, nbytes), str, nbytes);
+#endif
         }
         return NULL;
@@ -380 +600 @@
 char *pstmakestrspace(struct shinstance *psh, size_t minbytes, char *end)
 {
+#ifdef KASH_SEPARATE_PARSER_ALLOCATOR
+        pstack_block *pst = psh->curpstack;
+        size_t const len = end - pst->nextbyte;
+
+        assert(pst->avail - pst->strleft == len);
+        TRACE2((psh, "pstmakestrspace: len=%u minbytes=%u (=> %u)\n", len, minbytes, len + minbytes));
+
+        pstgrowblock(psh, pst, minbytes + len, len);
+
+        pst->strleft = pst->avail - len;
+        return pst->nextbyte + len;
+
+#else
         size_t const len = end - stackblock(psh);
+
         assert(stackblocksize(psh) - psh->sstrnleft == len);
-TRACE2((psh, "pstmakestrspace: len=%u minbytes=%u (=> %u)\n", len, minbytes, len + minbytes));
+        TRACE2((psh, "pstmakestrspace: len=%u minbytes=%u (=> %u)\n", len, minbytes, len + minbytes));
+
         minbytes += len;
         while (stackblocksize(psh) < minbytes)
                 growstackblock(psh);
+
         psh->sstrnleft = (int)(stackblocksize(psh) - len);
         return (char *)stackblock(psh) + len;
+#endif
 }
 
@@ -393 +630 @@
 char *pstputcgrow(shinstance *psh, char *end, char c)
 {
-        psh->sstrnleft++; /* PSTPUTC() already incremented it. */
+#ifdef KASH_SEPARATE_PARSER_ALLOCATOR
+        pstack_block *pst = psh->curpstack;
+        pst->strleft++;         /* PSTPUTC() already incremented it. */
+        end = pstmakestrspace(psh, 1, end);
+        assert(pst->strleft > 0);
+        pst->strleft--;
+#else
+        psh->sstrnleft++;       /* PSTPUTC() already incremented it. */
         end = pstmakestrspace(psh, 1, end);
         assert(psh->sstrnleft > 0);
         psh->sstrnleft--;
+#endif
         *end++ = c;
         return end;
@@ -404 +649 @@
 char *pstgrabstr(struct shinstance *psh, char *end)
 {
+#ifdef KASH_SEPARATE_PARSER_ALLOCATOR
+        pstack_block *pst = psh->curpstack;
+        char * const pstart = pst->nextbyte;
+        size_t nbytes = (size_t)(end - pstart);
+
+        assert((uintptr_t)end > (uintptr_t)pstart);
+        assert(end[-1] == '\0');
+        assert(SHELL_ALIGN((uintptr_t)pstart) == (uintptr_t)pstart);
+        assert(pst->avail - pst->strleft >= nbytes);
+
+        nbytes = SHELL_ALIGN(nbytes); /** @todo don't align strings, align the other allocations. */
+        pst->nextbyte += nbytes;
+        pst->avail    -= nbytes;
+        pst->strbytesalloced += nbytes;
+
+        return pstart;
+
+#else
         char * const pstart = stackblock(psh);
         size_t nbytes = (size_t)(end - pstart);
@@ -417 +680 @@
 
         return pstart;
-}
-
+#endif
+}
+