forked from nuttx/nuttx-update
fed3da9f03
The search algorithm does not work with the ctz approach at all, if there is a free range of granules that does not fit a specific allocation (i.e. the granule allocation is fragmented) it will cause an infinite loop as the algorithm will try to find free space from the same (free) starting granule, causing an infinite loop. The clz approach works for all cases, it will find the last used granule and the search will continue from the next free granule. Also, offsetting a full GAT must be sizeof(gat[0] - 1), which is 31 in this case. The reason is that the upper level search function increments the value by +1.
312 lines
6.8 KiB
C
312 lines
6.8 KiB
C
/****************************************************************************
|
|
* mm/mm_gran/mm_grantable.c
|
|
*
|
|
* SPDX-License-Identifier: Apache-2.0
|
|
*
|
|
* Licensed to the Apache Software Foundation (ASF) under one or more
|
|
* contributor license agreements. See the NOTICE file distributed with
|
|
* this work for additional information regarding copyright ownership. The
|
|
* ASF licenses this file to you under the Apache License, Version 2.0 (the
|
|
* "License"); you may not use this file except in compliance with the
|
|
* License. You may obtain a copy of the License at
|
|
*
|
|
* http://www.apache.org/licenses/LICENSE-2.0
|
|
*
|
|
* Unless required by applicable law or agreed to in writing, software
|
|
* distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
|
|
* WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
|
|
* License for the specific language governing permissions and limitations
|
|
* under the License.
|
|
*
|
|
****************************************************************************/
|
|
|
|
/****************************************************************************
|
|
* Included Files
|
|
****************************************************************************/
|
|
|
|
#include <nuttx/config.h>
|
|
|
|
#include <assert.h>
|
|
#include <errno.h>
|
|
#include <strings.h>
|
|
#include <debug.h>
|
|
|
|
#include <nuttx/bits.h>
|
|
#include <nuttx/mm/gran.h>
|
|
|
|
#include "mm_gran/mm_gran.h"
|
|
#include "mm_gran/mm_grantable.h"
|
|
|
|
#ifdef CONFIG_GRAN
|
|
|
|
/****************************************************************************
|
|
* Preprocessors
|
|
****************************************************************************/
|
|
|
|
#define GATCFULL 0xffffffffu /* a full GAT cell */
|
|
#define DEBRUJIN_NUM 0x077CB531UL /* the de Bruijn Sequence */
|
|
|
|
/****************************************************************************
|
|
* Private data
|
|
****************************************************************************/
|
|
|
|
#if !defined(CONFIG_HAVE_BUILTIN_CLZ) || !defined(CONFIG_HAVE_BUILTIN_CTZ)
|
|
|
|
/* The de Bruijn lookup table to get n from BIT(n). */
|
|
|
|
static const uint8_t DEBRUJIN_LUT[32] =
|
|
{
|
|
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
|
|
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
|
|
};
|
|
#endif
|
|
|
|
/****************************************************************************
|
|
* Private Functions
|
|
****************************************************************************/
|
|
|
|
/* return BIT(MSB(n)) */
|
|
|
|
uint32_t msb_mask(uint32_t n)
|
|
{
|
|
/* see https://www.geeksforgeeks.org/find-significant-set-bit-number */
|
|
|
|
DEBUGASSERT(n);
|
|
n |= n >> 1;
|
|
n |= n >> 2;
|
|
n |= n >> 4;
|
|
n |= n >> 8;
|
|
n |= n >> 16;
|
|
|
|
n = ((n + 1) >> 1) | (n & (1 << ((sizeof(n) << 3)-1)));
|
|
return n;
|
|
}
|
|
|
|
/* return BIT(LSB(n)) */
|
|
|
|
uint32_t lsb_mask(uint32_t n)
|
|
{
|
|
DEBUGASSERT(n);
|
|
return (-n & n) & GATCFULL;
|
|
}
|
|
|
|
/* set or clear a GAT cell with given bit mask */
|
|
|
|
static void cell_set(gran_t *gran, uint32_t cell, uint32_t mask, bool val)
|
|
{
|
|
if (val)
|
|
{
|
|
gran->gat[cell] |= mask;
|
|
}
|
|
else
|
|
{
|
|
gran->gat[cell] &= ~mask;
|
|
}
|
|
}
|
|
|
|
/* set or clear a range of GAT bits */
|
|
|
|
static void gran_set_(gran_t *gran, gatr_t *rang, bool val)
|
|
{
|
|
uint32_t c;
|
|
|
|
cell_set(gran, rang->sidx, rang->smask, val);
|
|
if (rang->sidx != rang->eidx)
|
|
{
|
|
cell_set(gran, rang->eidx, rang->emask, val);
|
|
c = rang->sidx + 1;
|
|
for (; c < rang->eidx; c++)
|
|
{
|
|
cell_set(gran, c, GATCFULL, val);
|
|
}
|
|
}
|
|
|
|
return;
|
|
}
|
|
|
|
/****************************************************************************
|
|
* Public Functions
|
|
****************************************************************************/
|
|
|
|
/* prepare given GAT range instance for later use. */
|
|
|
|
int gran_range(const gran_t *gran, size_t posi, size_t size,
|
|
gatr_t *rang)
|
|
{
|
|
if (!gran || gran->ngranules < posi + size)
|
|
{
|
|
return -EINVAL;
|
|
}
|
|
|
|
if (rang == NULL)
|
|
{
|
|
return -ENOMEM;
|
|
}
|
|
|
|
rang->width = GATC_BITS(gran);
|
|
|
|
rang->sidx = posi / rang->width;
|
|
rang->soff = posi % rang->width;
|
|
|
|
posi += size - 1;
|
|
rang->eidx = posi / GATC_BITS(gran);
|
|
rang->eoff = posi % GATC_BITS(gran);
|
|
|
|
rang->smask = ~(BIT(rang->soff) - 1);
|
|
rang->emask = (BIT(rang->eoff) - 1) | BIT(rang->eoff);
|
|
|
|
if (rang->sidx == rang->eidx)
|
|
{
|
|
rang->smask &= rang->emask; /* combine the masks */
|
|
rang->emask = rang->smask;
|
|
}
|
|
|
|
return OK;
|
|
}
|
|
|
|
/* checks if a range of granule matches the expected status */
|
|
|
|
bool gran_match(const gran_t *gran, size_t posi, size_t size, bool used,
|
|
size_t *mpos)
|
|
{
|
|
uint32_t c; /* cell index */
|
|
uint32_t v; /* masked cell value */
|
|
uint32_t e; /* expected cell value */
|
|
gatr_t r; /* range helper */
|
|
|
|
if (gran_range(gran, posi, size, &r) < 0)
|
|
{
|
|
memset(&r, 0, sizeof(r));
|
|
}
|
|
|
|
/* check the ending cell */
|
|
|
|
c = r.eidx;
|
|
e = used ? r.emask : 0 ;
|
|
v = gran->gat[c] & r.emask;
|
|
if (v != e)
|
|
{
|
|
goto failure;
|
|
}
|
|
|
|
if (r.sidx == r.eidx)
|
|
{
|
|
return true;
|
|
}
|
|
|
|
/* check cells in between */
|
|
|
|
c = r.eidx - 1;
|
|
e = used ? GATCFULL : 0;
|
|
for (; c > r.sidx; c--)
|
|
{
|
|
v = gran->gat[c];
|
|
if (v != e)
|
|
{
|
|
goto failure;
|
|
}
|
|
}
|
|
|
|
/* check the starting cell */
|
|
|
|
c = r.sidx;
|
|
e = used ? r.smask : 0 ;
|
|
v = gran->gat[c] & r.smask;
|
|
if (v != e)
|
|
{
|
|
goto failure;
|
|
}
|
|
|
|
return true;
|
|
|
|
failure:
|
|
|
|
if (mpos && !used)
|
|
{
|
|
size_t tmp;
|
|
|
|
v = gran->gat[c];
|
|
DEBUGASSERT(v);
|
|
|
|
if (v == GATCFULL)
|
|
{
|
|
/* Handle full GAT quickly */
|
|
|
|
tmp = 31;
|
|
}
|
|
else
|
|
{
|
|
/* offset of last used when matching for free */
|
|
|
|
#ifdef CONFIG_HAVE_BUILTIN_CLZ
|
|
tmp = 31 - __builtin_clz(v);
|
|
#else
|
|
tmp = (uint32_t)((msb_mask(v)) * DEBRUJIN_NUM) >> 27;
|
|
DEBUGASSERT(tmp < sizeof(DEBRUJIN_LUT));
|
|
tmp = DEBRUJIN_LUT[tmp];
|
|
#endif
|
|
}
|
|
|
|
/* return the last used position to caller */
|
|
|
|
*mpos = tmp + c * GATC_BITS(gran);
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
/* returns granule number of free range or negative error */
|
|
|
|
int gran_search(const gran_t *gran, size_t size)
|
|
{
|
|
int ret = -EINVAL;
|
|
|
|
if (gran == NULL || gran->ngranules < size)
|
|
{
|
|
return ret;
|
|
}
|
|
|
|
ret = -ENOMEM;
|
|
for (size_t i = 0; i <= gran->ngranules - size; i++)
|
|
{
|
|
if (gran_match(gran, i, size, 0, &i))
|
|
{
|
|
ret = i;
|
|
break;
|
|
}
|
|
}
|
|
|
|
return ret;
|
|
}
|
|
|
|
/* set a range of granules */
|
|
|
|
int gran_set(gran_t *gran, size_t posi, size_t size)
|
|
{
|
|
gatr_t rang;
|
|
int ret = gran_range(gran, posi, size, &rang);
|
|
|
|
if (ret == OK)
|
|
{
|
|
gran_set_(gran, &rang, true);
|
|
}
|
|
|
|
return ret;
|
|
}
|
|
|
|
/* clear a range of granules */
|
|
|
|
int gran_clear(gran_t *gran, size_t posi, size_t size)
|
|
{
|
|
gatr_t rang;
|
|
int ret = gran_range(gran, posi, size, &rang);
|
|
|
|
if (ret == OK)
|
|
{
|
|
gran_set_(gran, &rang, false);
|
|
}
|
|
|
|
return ret;
|
|
}
|
|
|
|
#endif /* CONFIG_GRAN */
|