Add beginning of a simple granule allocator to support DMA IO buffer allocation

git-svn-id: svn://svn.code.sf.net/p/nuttx/code/trunk@5129 42af7a65-404d-4744-a932-0658087f49c3

4 files changed, 622 insertions, 0 deletions

diff --git a/nuttx/mm/mm_gran.h b/nuttx/mm/mm_gran.h
new file mode 100644
index 000000000..6f5f890ed
--- /dev/null
+++ b/nuttx/mm/mm_gran.h
@@ -0,0 +1,84 @@
+/****************************************************************************
+ * mm/mm_gran.h
+ *
+ *   Copyright (C) 2012 Gregory Nutt. All rights reserved.
+ *   Author: Gregory Nutt <gnutt@nuttx.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name NuttX nor the names of its contributors may be
+ *    used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
+ * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ ****************************************************************************/
+
+#ifndef __MM_MM_GRAN_H
+#define __MM_MM_GRAN_H
+
+/****************************************************************************
+ * Included Files
+ ****************************************************************************/
+
+#include <nuttx/config.h>
+
+#include <nuttx/gran.h>
+
+/****************************************************************************
+ * Pre-processor Definitions
+ ****************************************************************************/
+
+#define SIZEOF_GAT(n) \
+  ((n + 31) >> 5)
+#define SIZEOF_GRAN_S(n) \
+  (sizeof(struct gran_s) + sizeof(uint32_t) * (SIZEOF_GAT(n) - 1))
+
+/****************************************************************************
+ * Public Types
+ ****************************************************************************/
+
+/* This structure represents the state of on granual allocation */
+
+struct gran_s
+{
+  uint8_t    log2gran;  /* Log base 2 of the size of one granule */
+  uint16_t   ngranules; /* The total number of (aligned) granules in the heap */
+  uintptr_t  heapstart; /* The aligned start of the granule heap */
+  uint32_t   gat[i];    /* Start of the granule allocation table */
+};
+
+/****************************************************************************
+ * Public Data
+ ****************************************************************************/
+
+/* State of the single GRAN allocator */
+
+#ifdef CONFIG_GRAN_SINGLE
+extern FAR struct gran_s *g_graninfo;
+#endif
+
+/****************************************************************************
+ * Public Function Prototypes
+ ****************************************************************************/
+
+#endif /* __MM_MM_GRAN_H */
diff --git a/nuttx/mm/mm_granalloc.c b/nuttx/mm/mm_granalloc.c
new file mode 100644
index 000000000..f94f447e3
--- /dev/null
+++ b/nuttx/mm/mm_granalloc.c
@@ -0,0 +1,241 @@
+/****************************************************************************
+ * mm/mm_granalloc.c
+ *
+ *   Copyright (C) 2012 Gregory Nutt. All rights reserved.
+ *   Author: Gregory Nutt <gnutt@nuttx.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name NuttX nor the names of its contributors may be
+ *    used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
+ * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ ****************************************************************************/
+
+/****************************************************************************
+ * Included Files
+ ****************************************************************************/
+
+#include <nuttx/config.h>
+
+#include <nuttx/gran.h>
+
+/****************************************************************************
+ * Pre-processor Definitions
+ ****************************************************************************/
+
+/****************************************************************************
+ * Name: gran_common_alloc
+ *
+ * Description:
+ *   Allocate memory from the granule heap.
+ *
+ * Input Parameters:
+ *   priv  - The granule heap state structure.
+ *   alloc - The adress of the allocation.
+ *   ngranules - The number of granules allocated
+ *
+ * Returned Value:
+ *   None
+ *
+ ****************************************************************************/
+
+static inline FAR void *gran_mark_allocated(FAR struct gran_s *priv, uintptr_t alloc, unsigned int ngranules)
+{
+  unsigned int granno;
+  unsigned int gatidx;
+  unsigned int gatbit;
+  unsigned int avail;
+  uint32_t mask;
+
+  /* Determine the granule number of the allocation */
+
+  granno = (alloc - priv->heapstart) >> priv->log2gran;
+
+  /* Determine the GAT table index associated with the allocation */
+
+  gatidx = granno >> 5;
+  gatbit = granno & 31;
+
+  /* Mark bits in the first GAT entry */
+
+  avail = 32 - gatbit;
+  if (ngranules > avail)
+    {
+      priv->gat[gatidx] |= (0xffffffff << gatbit);
+      ngranules -= avail;
+    }
+
+  /* Handle the cae where where all of the granules come from one entry */
+
+  else
+    {
+      mask = 0xffffffff >> (32 - ngranules);
+      priv->gat[gatidx] |= (mask << gatbit);
+      return;
+    }
+
+  /* Mark bits in the second GAT entry */
+
+  mask = 0xffffffff >> (32 - ngranules);
+  priv->gat[gatidx+1] |= (mask << gatbit);
+}
+
+/****************************************************************************
+ * Name: gran_common_alloc
+ *
+ * Description:
+ *   Allocate memory from the granule heap.
+ *
+ * Input Parameters:
+ *   priv - The granule heap state structure.
+ *   size - The size of the memory region to allocate.
+ *
+ * Returned Value:
+ *   On success, a non-NULL pointer to the allocated memory is returned.
+ *
+ ****************************************************************************/
+
+static inline FAR void *gran_common_alloc(FAR struct gran_s *priv, size_t size)
+{
+  unsigned int ngranules;
+  size_t       tmpmask;
+  uintptr_t     alloc;
+  uint32_t      curr;
+  uint32_t      next;
+  uint32_t      mask;
+  int           i;
+  int           j;
+
+  DEBUGASSERT(priv);
+  if (priv && size > 0)
+    {
+      /* How many contiguous granules we we need to find? */
+
+      tmpmask   = (1 << log2gran) - 1;
+      ngranules = (size + tmpmask) >> log2gran;
+
+      /* Then create mask for that number of granules */
+
+      DEBUGASSERT(ngranules <= 32);
+      mask = 0xffffffff >> (32 - ngranules);
+
+      /* Now search the granule allocation table for that number of contiguous */
+
+      alloc = priv->heapstart;
+
+      for (i = 0; i < priv->ngranules; i += 32)
+        {
+          /* Get the GAT index associated with the granule (i) */
+
+          j = i >> 5;
+          curr  = priv->gat[j];
+
+          /* Get the next entry from the GAT to support a 64 bit shift */
+
+          if (i < priv->ngranules)
+            {
+              next = priv->gat[j + 1];
+            }
+
+          /* Use all zeroes when are at the last entry in the GAT */
+
+          else
+            {
+              next = 0;
+            }
+
+          for (j = 0; j < 32; j++)
+            {
+              /* Check if we have the allocation at this bit position (0
+               * means unallocated).
+               */
+
+              if ((curr & mask) == 0)
+                {
+                  /* Yes.. mark these granules allocated */
+
+                  gran_mark_allocated(priv, alloc, ngranules);
+
+                  /* And return the allocation address */
+
+                  return (FAR void *)alloc;
+                }
+
+              /* Set up for the next time through the loop.  Perform a 64
+               * bit shift to move to the next gram position.
+               */
+
+              curr >>= 1;
+              if (next & 1)
+                {
+                  curr |= 0x80000000;
+                }
+              next >> 1;
+
+              /* Increment the next candidate allocation address */
+
+              alloc += (1 << priv->log2gran);
+            }
+        }
+    }
+
+  return NULL;
+}
+
+/****************************************************************************
+ * Global Functions
+ ****************************************************************************/
+
+/****************************************************************************
+ * Name: gran_alloc
+ *
+ * Description:
+ *   Allocate memory from the granule heap.
+ *
+ *   NOTE: The current implementation also restricts the maximum allocation
+ *   size to 32 granaules.  That restriction could be eliminated with some
+ *   additional coding effort.
+ *
+ * Input Parameters:
+ *   handle - The handle previously returned by gran_initialize
+ *   size   - The size of the memory region to allocate.
+ *
+ * Returned Value:
+ *   On success, either a non-NULL pointer to the allocated memory (if
+ *   CONFIG_GRAN_SINGLE) or zero  (if !CONFIG_GRAN_SINGLE) is returned.
+ *
+ ****************************************************************************/
+
+#ifdef CONFIG_GRAN_SINGLE
+FAR void *gran_alloc(size_t size)
+{
+  return gran_common_alloc(g_graninfo, size);
+}
+#else
+FAR void *gran_alloc(GRAN_HANDLE handle, size_t size)
+{
+  return gran_common_alloc((FAR struct gran_s *)handle, size);
+}
+#endif
diff --git a/nuttx/mm/mm_granfree.c b/nuttx/mm/mm_granfree.c
new file mode 100644
index 000000000..4679ae62b
--- /dev/null
+++ b/nuttx/mm/mm_granfree.c
@@ -0,0 +1,134 @@
+/****************************************************************************
+ * mm/mm_granfree.c
+ *
+ *   Copyright (C) 2012 Gregory Nutt. All rights reserved.
+ *   Author: Gregory Nutt <gnutt@nuttx.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name NuttX nor the names of its contributors may be
+ *    used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
+ * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ ****************************************************************************/
+
+/****************************************************************************
+ * Included Files
+ ****************************************************************************/
+
+#include <nuttx/config.h>
+
+#include <nuttx/gran.h>
+
+/****************************************************************************
+ * Pre-processor Definitions
+ ****************************************************************************/
+
+/****************************************************************************
+ * Name: gran_common_free
+ *
+ * Description:
+ *   Return memory to the granule heap.
+ *
+ * Input Parameters:
+ *   handle - The handle previously returned by gran_initialize
+ *   memory - A pointer to memory previoiusly allocated by gran_alloc.
+ *
+ * Returned Value:
+ *   None
+ *
+ ****************************************************************************/
+
+static inline void gran_common_free(FAR struct gran_s *priv,
+                                    FAR void *memory, size_t size)
+{
+  unsigned int granno;
+  unsigned int gatidx;
+  unsigned int gatbit;
+  unsigned int avail;
+  uint32_t mask;
+
+  /* Determine the granule number of the allocation */
+
+  granno = (alloc - priv->heapstart) >> priv->log2gran;
+
+  /* Determine the GAT table index associated with the allocation */
+
+  gatidx = granno >> 5;
+  gatbit = granno & 31;
+
+  /* Clear bits in the first GAT entry */
+
+  avail = 32 - gatbit;
+  if (ngranules > avail)
+    {
+      priv->gat[gatidx] &= ~(0xffffffff << gatbit);
+      ngranules -= avail;
+    }
+
+  /* Handle the cae where where all of the granules came from one entry */
+
+  else
+    {
+      mask = 0xffffffff >> (32 - ngranules);
+      priv->gat[gatidx] &= ~(mask << gatbit);
+      return;
+    }
+
+  /* Clear bits in the second GAT entry */
+
+  mask = 0xffffffff >> (32 - ngranules);
+  priv->gat[gatidx+1] &= ~(mask << gatbit);
+}
+
+/****************************************************************************
+ * Global Functions
+ ****************************************************************************/
+
+/****************************************************************************
+ * Name: gran_free
+ *
+ * Description:
+ *   Return memory to the granule heap.
+ *
+ * Input Parameters:
+ *   handle - The handle previously returned by gran_initialize
+ *   memory - A pointer to memory previoiusly allocated by gran_alloc.
+ *
+ * Returned Value:
+ *   None
+ *
+ ****************************************************************************/
+
+#ifdef CONFIG_GRAN_SINGLE
+void gran_free(FAR void *memory, size_t size)
+{
+  return gran_common_free(g_graninfo, memory, size);
+}
+#else
+void gran_free(GRAN_HANDLE handle, FAR void *memory, size_t size)
+{
+  return gran_common_free((FAR struct gran_s *)handle, memory, size);
+}
+#endif
diff --git a/nuttx/mm/mm_graninit.c b/nuttx/mm/mm_graninit.c
new file mode 100644
index 000000000..99b499155
--- /dev/null
+++ b/nuttx/mm/mm_graninit.c
@@ -0,0 +1,163 @@
+/****************************************************************************
+ * mm/mm_graninit.c
+ *
+ *   Copyright (C) 2012 Gregory Nutt. All rights reserved.
+ *   Author: Gregory Nutt <gnutt@nuttx.org>
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in
+ *    the documentation and/or other materials provided with the
+ *    distribution.
+ * 3. Neither the name NuttX nor the names of its contributors may be
+ *    used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS
+ * OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
+ * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+ * POSSIBILITY OF SUCH DAMAGE.
+ *
+ ****************************************************************************/
+
+/****************************************************************************
+ * Included Files
+ ****************************************************************************/
+
+#include <nuttx/config.h>
+
+#include <nuttx/gran.h>
+
+/****************************************************************************
+ * Pre-processor Definitions
+ ****************************************************************************/
+
+/****************************************************************************
+ * Public Data
+ ****************************************************************************/
+
+/* State of the single GRAN allocator */
+
+#ifdef CONFIG_GRAN_SINGLE
+FAR struct gran_s *g_graninfo;
+#endif
+
+/****************************************************************************
+ * Private Functions
+ ****************************************************************************/
+
+/****************************************************************************
+ * Name: gran_common_initialize
+ *
+ * Description:
+ *   Perfrom common GRAN initialization.
+ *
+ * Input Parameters:
+ *   info      - Private granule data structure pointer
+ *   heapstart - Start of the granule allocation heap
+ *   heapsize  - Size of heap in bytes
+ *   log2gran  - Log base 2 of the size of one granule.  0->1 byte,
+ *               1->2 bytes, 2->4 bytes, 3-> 8bytes, etc.
+ *
+ * Returned Value:
+ *   On success, a non-NULL info structure is returned that may be used with
+ *   other granule allocator interfaces.
+ *
+ ****************************************************************************/
+
+static inline FAR struct gran_s *gran_common_initialize(FAR void *heapstart,
+                                                        size_t heapsize,
+                                                        uint8_t log2gran)
+{
+  FAR struct gran_s *priv;
+  uintptr_t          heapend;
+  uintptr_t          alignedstart;
+  unsigned int       mask;
+  unsigned int       alignedsize;
+  unsigned int       ngranules;
+
+  /* Determine the number of granules */
+
+  mask         = (1 << log2gran) - 1;
+  heapend      = (uintptr_t)heapstart + heapsize;
+  alignedstart = ((uintptr_t)heapstart + mask) & ~mask;
+  alignedsize  = (heapend - alignedstart) & ~mask;
+  ngranules    = alignedsize >> log2gran;
+
+  /* Allocate the information structure with a granule table of the
+   * correct size.
+   */
+
+  priv = ( FAR struct gran_s *)zalloc(SIZEOF_GRAN_S(ngranules));
+  if (priv)
+    {
+      /* Initialize non-zero elements of the granules heap info structure */
+
+      priv->log2gran  = log2gran;
+      priv->ngranules = ngranules;
+      priv->heapstart = alignedstart
+    }
+
+  return priv;
+}
+
+/****************************************************************************
+ * Public Functions
+ ****************************************************************************/
+
+/****************************************************************************
+ * Name: gran_initialize
+ *
+ * Description:
+ *   Set up one granule allocator instance.  Allocations will be aligned to
+ *   the granule size; allocations will be in units of the granule size.
+ *   Larger granules will give better performance and less overhead but more
+ *   losses of memory due to alignment and quantization waste.
+ *
+ *   NOTE: The current implementation also restricts the maximum allocation
+ *   size to 32 granaules.  That restriction could be eliminated with some
+ *   additional coding effort.
+ *
+ * Input Parameters:
+ *   heapstart - Start of the granule allocation heap
+ *   heapsize  - Size of heap in bytes
+ *   log2gran  - Log base 2 of the size of one granule.  0->1 byte,
+ *               1->2 bytes, 2->4 bytes, 3-> 8bytes, etc.
+ *
+ * Returned Value:
+ *   On success, a non-NULL handle is returned that may be used with other
+ *   granual allocator interfaces.
+ *
+ ****************************************************************************/
+
+#ifdef CONFIG_GRAN_SINGLE
+int gran_initialize(FAR void *heapstart, size_t heapsize, uint8_t log2gran)
+{
+  g_graninfo = gran_common_initialize(heapstart, heapsize, log2gran);
+  if (!g_granifo)
+    {
+      return -ENOMEM;
+    }
+
+  return OK;
+}
+#else
+GRAN_HANDLE gran_initialize(FAR void *heapstart, size_t heapsize, uint8_t log2gran)
+{
+  return (GRAN_HANDLE)gran_common_initialize(heapstart, heapsize, log2gran);
+}
+#endif
+