123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627 |
- /****************************************************************************
- * mm/mm_gran/mm_graninfo.c
- *
- * 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 <nuttx/mm/gran.h>
- #include "mm_gran/mm_gran.h"
- #ifdef CONFIG_GRAN
- /****************************************************************************
- * Private Data
- ****************************************************************************/
- struct nibble_info_s
- {
- uint16_t nfree : 4; /* Total bits free in a nibble */
- uint16_t nlsfree : 4; /* Total contiguous LS bits free */
- uint16_t nmsfree : 4; /* Total contiguous MS bits free */
- uint16_t mxfree : 4; /* Largest internal contiguous bits free */
- };
- struct valinfo_s
- {
- uint8_t nfree; /* Total bits free in the byte/hword */
- uint8_t nlsfree; /* Total contiguous LS bits free */
- uint8_t nmsfree; /* Total contiguous MS bits free */
- uint8_t mxfree; /* Largest internal contiguous bits free */
- };
- /****************************************************************************
- * Private Data
- ****************************************************************************/
- static const struct nibble_info_s g_0bit_info[1] =
- {
- { /* 0 xxxx */
- 0, 0, 0, 0
- }
- };
- static const struct nibble_info_s g_1bit_info[2] =
- {
- { /* 0 xxx0 */
- 1, 1, 0, 0
- },
- { /* 1 xxx1 */
- 0, 0, 0, 0
- }
- };
- static const struct nibble_info_s g_2bit_info[4] =
- {
- { /* 0 xx00 */
- 2, 2, 0, 0
- },
- { /* 1 xx01 */
- 1, 0, 1, 0
- },
- { /* 2 xx10 */
- 1, 1, 0, 0
- },
- { /* 3 xx11 */
- 0, 0, 0, 0
- }
- };
- static const struct nibble_info_s g_3bit_info[8] =
- {
- { /* 0 x000 */
- 3, 3, 0, 0
- },
- { /* 1 x001 */
- 2, 0, 2, 0
- },
- { /* 2 x010 */
- 2, 1, 1, 0
- },
- { /* 3 x011 */
- 1, 0, 1, 0
- },
- { /* 4 x100 */
- 2, 2, 0, 0
- },
- { /* 5 x101 */
- 1, 0, 0, 1
- },
- { /* 6 x110 */
- 1, 1, 0, 0
- },
- { /* 7 x111 */
- 0, 0, 0, 0
- }
- };
- static const struct nibble_info_s g_4bit_info[16] =
- {
- { /* 0 0000 */
- 4, 4, 0, 0
- },
- { /* 1 0001 */
- 3, 0, 3, 0
- },
- { /* 2 0010 */
- 3, 1, 2, 0
- },
- { /* 3 0011 */
- 2, 0, 2, 0
- },
- { /* 4 0100 */
- 3, 2, 1, 0
- },
- { /* 5 0101 */
- 2, 0, 1, 1
- },
- { /* 6 0110 */
- 2, 1, 1, 0
- },
- { /* 7 0111 */
- 1, 0, 1, 0
- },
- { /* 8 1000 */
- 3, 3, 0, 0
- },
- { /* 9 1001 */
- 2, 0, 0, 2
- },
- { /* 10 1010 */
- 2, 1, 0, 1
- },
- { /* 11 1011 */
- 1, 0, 0, 1
- },
- { /* 12 1100 */
- 2, 2, 0, 0
- },
- { /* 13 1101 */
- 1, 0, 0, 1
- },
- { /* 14 1110 */
- 1, 1, 0, 0
- },
- { /* 15 1111 */
- 0, 0, 0, 0
- }
- };
- static const struct nibble_info_s *g_info_table[5] =
- {
- g_0bit_info,
- g_1bit_info,
- g_2bit_info,
- g_3bit_info,
- g_4bit_info
- };
- /****************************************************************************
- * Private Functions
- ****************************************************************************/
- /****************************************************************************
- * Name: gran_nibble_info
- *
- * Description:
- * Return information for a 4-bit value from the GAT.
- *
- * Input Parameters:
- * value - The 4-bit value
- * info - The location to return the hword info
- * nbits - Number of valid bits in value
- *
- * Returned Value:
- * None
- *
- ****************************************************************************/
- static void gran_nibble_info(uint8_t value, FAR struct valinfo_s *info,
- unsigned int nbits)
- {
- FAR const struct nibble_info_s *table = g_info_table[nbits];
- FAR const struct nibble_info_s *nibinfo;
- uint8_t mask;
- /* Look up the table entry */
- mask = ((1 << nbits) - 1);
- value &= mask;
- nibinfo = &table[value];
- /* Return expanded values */
- info->nfree = nibinfo->nfree;
- info->nlsfree = nibinfo->nlsfree;
- info->nmsfree = nibinfo->nmsfree;
- info->mxfree = nibinfo->mxfree;
- }
- /****************************************************************************
- * Name: gran_info_combine
- *
- * Description:
- * Combine new MS bit information with existing LS bit information.
- *
- * Input Parameters:
- * msinfo - The new MS bit information
- * msbits - Number of bits in MS piece
- * lsinfo - The existing LS bit information
- *
- * Returned Value:
- * None
- *
- ****************************************************************************/
- static void gran_info_combine(FAR const struct valinfo_s *msinfo,
- unsigned int msbits,
- FAR struct valinfo_s *lsinfo,
- unsigned int lsbits)
- {
- unsigned int midfree;
- /* Is there a region of free space isolated in the middle of the two
- * pieces?
- */
- if (lsinfo->nlsfree < lsbits && msinfo->nlsfree < msbits)
- {
- /* Yes... combine the MS free bits from the LS piece with the
- * LS free bits from the MS piece.
- */
- midfree = lsinfo->nmsfree + msinfo->nlsfree;
- }
- else
- {
- midfree = 0;
- }
- /* Update the total number of free bits in the combined pieces */
- lsinfo->nfree += msinfo->nfree;
- /* Figure out how many MS bits will now be free. First, is the MS piece
- * all free?
- */
- if (msinfo->nlsfree == msbits)
- {
- /* Yes.. is the LS piece also all free bits? */
- if (lsinfo->nlsfree == lsbits)
- {
- /* Yes.. the there are no MS free bits (only LS) */
- lsinfo->nmsfree = 0;
- }
- else
- {
- /* No.. then combine all of the bits from the MS piece with the
- * MS bits of the LS piece.
- */
- lsinfo->nmsfree += msbits;
- }
- }
- else
- {
- /* No.. then just replace the MS bits of the LS piece with the MS
- * bits from the new MS piece.
- */
- lsinfo->nmsfree = msinfo->nmsfree;
- }
- /* Figure out how many LS bits will now be free. First, is the LS piece
- * all free?
- */
- if (lsinfo->nlsfree == lsbits)
- {
- /* Yes.. then combine all of the bits from the LS piece with the
- * LS bits of the MS piece.
- */
- lsinfo->nlsfree += msinfo->nlsfree;
- }
- /* Now, what is the longest internal sequence of the free bits? It might
- * be original sequence of free bits in the LS piece. Or it might the
- * section of middle bits that got above.
- */
- if (midfree > lsinfo->mxfree)
- {
- lsinfo->mxfree = midfree;
- }
- /* Or it might the section of middle bits in the new MS piece */
- if (msinfo->mxfree > lsinfo->mxfree)
- {
- lsinfo->mxfree = msinfo->mxfree;
- }
- }
- /****************************************************************************
- * Name: gran_byte_info
- *
- * Description:
- * Return information a 8-bit value from the GAT.
- *
- * Input Parameters:
- * value - The 16-bit value
- * info - The location to return the hword info
- * nbits - Number of valid bits in value
- *
- * Returned Value:
- * None
- *
- ****************************************************************************/
- static void gran_byte_info(uint8_t value, FAR struct valinfo_s *info,
- unsigned int nbits)
- {
- uint8_t mask;
- if (nbits < 8)
- {
- mask = ((1 << nbits) - 1);
- value &= mask;
- }
- else
- {
- mask = 0xff;
- }
- /* Handle special cases */
- if (value == 0)
- {
- /* All free */
- info->nfree = nbits;
- info->nlsfree = nbits;
- info->nmsfree = 0;
- info->mxfree = 0;
- }
- else if (value == mask)
- {
- /* All allocated */
- info->nfree = 0;
- info->nlsfree = 0;
- info->nmsfree = 0;
- info->mxfree = 0;
- }
- else
- {
- /* Some allocated */
- gran_nibble_info(value & 0x0f, info, nbits > 4 ? 4 : nbits);
- if (nbits > 4)
- {
- struct valinfo_s msinfo;
- unsigned int msbits = nbits - 4;
- gran_nibble_info(value >> 4, &msinfo, msbits);
- gran_info_combine(&msinfo, msbits, info, 4);
- }
- }
- }
- /****************************************************************************
- * Name: gran_hword_info
- *
- * Description:
- * Return information a 16-bit value from the GAT.
- *
- * Input Parameters:
- * value - The 16-bit value
- * info - The location to return the hword info
- * nbits - Number of valid bits in value
- *
- * Returned Value:
- * None
- *
- ****************************************************************************/
- static void gran_hword_info(uint16_t value, FAR struct valinfo_s *info,
- unsigned int nbits)
- {
- uint16_t mask;
- if (nbits < 16)
- {
- mask = ((1 << nbits) - 1);
- value &= mask;
- }
- else
- {
- mask = 0xffff;
- }
- /* Handle special cases */
- if (value == 0)
- {
- /* All free */
- info->nfree = nbits;
- info->nlsfree = nbits;
- info->nmsfree = 0;
- info->mxfree = 0;
- }
- else if (value == mask)
- {
- /* All allocated */
- info->nfree = 0;
- info->nlsfree = 0;
- info->nmsfree = 0;
- info->mxfree = 0;
- }
- else
- {
- /* Some allocated */
- gran_byte_info((uint8_t)(value & 0xff), info, nbits > 8 ? 8 : nbits);
- if (nbits > 8)
- {
- struct valinfo_s msinfo;
- unsigned int msbits = nbits - 8;
- gran_byte_info((uint8_t)(value >> 8), &msinfo, msbits);
- gran_info_combine(&msinfo, msbits, info, 8);
- }
- }
- }
- /****************************************************************************
- * Public Functions
- ****************************************************************************/
- /****************************************************************************
- * Name: gran_info
- *
- * Description:
- * Return information about the granule heap.
- *
- * Input Parameters:
- * handle - The handle previously returned by gran_initialize
- * info - Memory location to return the gran allocator info.
- *
- * Returned Value:
- * Zero (OK) is returned on success; a negated errno value is return on
- * any failure.
- *
- ****************************************************************************/
- void gran_info(GRAN_HANDLE handle, FAR struct graninfo_s *info)
- {
- FAR struct gran_s *priv = (FAR struct gran_s *)handle;
- uint32_t mask;
- uint32_t value;
- uint16_t mxfree;
- unsigned int nbits;
- unsigned int granidx;
- unsigned int gatidx;
- int ret;
- DEBUGASSERT(priv != NULL && info != NULL);
- info->log2gran = priv->log2gran;
- info->ngranules = priv->ngranules;
- info->nfree = 0;
- info->mxfree = 0;
- mxfree = 0;
- /* Get exclusive access to the GAT */
- ret = gran_enter_critical(priv);
- if (ret < 0)
- {
- /* Should happen only on task cancellation */
- DEBUGASSERT(ret == -ECANCELED);
- return;
- }
- /* Traverse the granule allocation */
- for (granidx = 0; granidx < priv->ngranules; granidx += 32)
- {
- /* Get the GAT index associated with the granule table entry */
- gatidx = granidx >> 5;
- value = priv->gat[gatidx];
- /* The final entry is a special case */
- if ((granidx + 32) > priv->ngranules)
- {
- nbits = priv->ngranules - granidx;
- mask = ((1ul << nbits) - 1);
- value &= mask;
- }
- else
- {
- nbits = 32;
- mask = 0xffffffff;
- }
- /* Handle the 32-bit cases */
- if (value == mask)
- {
- /* All allocated. This will terminate any sequence of free
- * granules.
- */
- if (mxfree > info->mxfree)
- {
- info->mxfree = mxfree;
- }
- mxfree = 0;
- }
- else if (value == 0x00000000)
- {
- /* All free */
- info->nfree += nbits;
- mxfree += nbits;
- }
- else
- {
- struct valinfo_s hwinfo;
- /* Some allocated */
- gran_hword_info((uint16_t)(value & 0xffff), &hwinfo,
- nbits > 16 ? 16 : nbits);
- if (nbits > 16)
- {
- struct valinfo_s msinfo;
- unsigned int msbits = nbits - 16;
- gran_hword_info((uint16_t)(value >> 16), &msinfo, msbits);
- gran_info_combine(&msinfo, msbits, &hwinfo, 16);
- }
- /* Update the running free sequence of granules */
- if (hwinfo.nlsfree > 0)
- {
- mxfree += hwinfo.nlsfree;
- }
- /* If the entire word is not free, then update the maxfree free
- * sequence.
- */
- if (hwinfo.nlsfree < nbits)
- {
- /* Is the sequence internally free bits in the 32-bit value
- * longer than the running free sequence?
- */
- if (hwinfo.mxfree > mxfree)
- {
- mxfree = hwinfo.mxfree;
- }
- /* Is the running free sequence longer than the last sequence
- * that we saw?
- */
- if (mxfree > info->mxfree)
- {
- info->mxfree = mxfree;
- }
- /* Then restart with the free MS granules */
- mxfree = hwinfo.nmsfree;
- }
- /* Update the total number of free granules */
- info->nfree += hwinfo.nfree;
- }
- }
- /* Check if the last, unterminated sequence of free granules was the longest */
- if (mxfree > info->mxfree)
- {
- info->mxfree = mxfree;
- }
- gran_leave_critical(priv);
- }
- #endif /* CONFIG_GRAN */
|