From 48026bb824fd2d9cfb00ecd040db6ef3a416bae9 Mon Sep 17 00:00:00 2001 From: Clyne Sullivan Date: Fri, 22 Jan 2021 21:43:36 -0500 Subject: upload initial port --- ChibiOS_20.3.2/os/oslib/src/chobjcaches.c | 491 ++++++++++++++++++++++++++++++ 1 file changed, 491 insertions(+) create mode 100644 ChibiOS_20.3.2/os/oslib/src/chobjcaches.c (limited to 'ChibiOS_20.3.2/os/oslib/src/chobjcaches.c') diff --git a/ChibiOS_20.3.2/os/oslib/src/chobjcaches.c b/ChibiOS_20.3.2/os/oslib/src/chobjcaches.c new file mode 100644 index 0000000..d08421b --- /dev/null +++ b/ChibiOS_20.3.2/os/oslib/src/chobjcaches.c @@ -0,0 +1,491 @@ +/* + ChibiOS - Copyright (C) 2006..2019 Giovanni Di Sirio. + + This file is part of ChibiOS. + + ChibiOS is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + ChibiOS is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see . +*/ + +/** + * @file oslib/src/chobjcaches.c + * @brief Objects Caches code. + * @details Objects caches. + *

Operation mode

+ * An object cache allows to retrieve and release objects from a + * slow media, for example a disk or flash.
+ * The most recently used objects are kept in a series of RAM + * buffers making access faster. Objects are identified by a + * pair which could be mapped, for example, to a + * disk drive identifier and sector identifier.
+ * Read and write operations are performed using externally-supplied + * functions, the cache is device-agnostic.
+ * The cache uses internally an hash table, the size of the table + * should be dimensioned to minimize the risk of hash collisions, + * a factor of two is usually acceptable, it depends on the specific + * application requirements.
+ * Operations defined for caches: + * - Get Object: Retrieves an object from cache, if not + * present then an empty buffer is returned. + * - Read Object: Retrieves an object from cache, if not + * present a buffer is allocated and the object is read from the + * media. + * - Release Object: Releases an object to the cache handling + * the media update, if required. + * . + * @pre In order to use the pipes APIs the @p CH_CFG_USE_OBJ_CACHES + * option must be enabled in @p chconf.h. + * @note Compatible with RT and NIL. + * + * @addtogroup oslib_objchaches + * @{ + */ + +#include "ch.h" + +#if (CH_CFG_USE_OBJ_CACHES == TRUE) || defined(__DOXYGEN__) + +/*===========================================================================*/ +/* Module local definitions. */ +/*===========================================================================*/ + +/* Default hash function.*/ +#if !defined(OC_HASH_FUNCTION) || defined(__DOXYGEN__) +#define OC_HASH_FUNCTION(ocp, group, key) \ + (((unsigned)(group) + (unsigned)(key)) & ((unsigned)(ocp)->hashn - 1U)) +#endif + +/* Insertion into an hash slot list.*/ +#define HASH_INSERT(ocp, objp, group, key) { \ + oc_hash_header_t *hhp; \ + (hhp) = &(ocp)->hashp[OC_HASH_FUNCTION(ocp, group, key)]; \ + (objp)->hash_next = (hhp)->hash_next; \ + (objp)->hash_prev = (oc_object_t *)(hhp); \ + (hhp)->hash_next->hash_prev = (objp); \ + (hhp)->hash_next = (objp); \ +} + +/* Removal of an object from the hash.*/ +#define HASH_REMOVE(objp) { \ + (objp)->hash_prev->hash_next = (objp)->hash_next; \ + (objp)->hash_next->hash_prev = (objp)->hash_prev; \ +} + +/* Insertion on LRU list head (newer objects).*/ +#define LRU_INSERT_HEAD(ocp, objp) { \ + (objp)->lru_next = (ocp)->lru.lru_next; \ + (objp)->lru_prev = (oc_object_t *)&(ocp)->lru; \ + (ocp)->lru.lru_next->lru_prev = (objp); \ + (ocp)->lru.lru_next = (objp); \ +} + +/* Insertion on LRU list head (newer objects).*/ +#define LRU_INSERT_TAIL(ocp, objp) { \ + (objp)->lru_prev = (ocp)->lru.lru_prev; \ + (objp)->lru_next = (oc_object_t *)&(ocp)->lru; \ + (ocp)->lru.lru_prev->lru_next = (objp); \ + (ocp)->lru.lru_prev = (objp); \ +} + +/* Removal of an object from the LRU list.*/ +#define LRU_REMOVE(objp) { \ + (objp)->lru_prev->lru_next = (objp)->lru_next; \ + (objp)->lru_next->lru_prev = (objp)->lru_prev; \ +} + +/*===========================================================================*/ +/* Module exported variables. */ +/*===========================================================================*/ + +/*===========================================================================*/ +/* Module local types. */ +/*===========================================================================*/ + +/*===========================================================================*/ +/* Module local variables. */ +/*===========================================================================*/ + +/*===========================================================================*/ +/* Module local functions. */ +/*===========================================================================*/ + +/** + * @brief Returns an object pointer from the cache, if present. + * + * @param[out] ocp pointer to the @p objects_cache_t structure to be + * @param[in] group object group identifier + * @param[in] key object identifier within the group + * initialized + * @return The pointer to the retrieved object. + * @retval NULL if the object is not in cache. + * + * @notapi + */ +static oc_object_t *hash_get_s(objects_cache_t *ocp, + uint32_t group, + uint32_t key) { + oc_hash_header_t *hhp; + oc_object_t *objp; + + /* Hash slot where to search for an hit.*/ + hhp = &ocp->hashp[OC_HASH_FUNCTION(ocp, group, key)]; + objp = hhp->hash_next; + + /* Scanning the siblings collision list.*/ + while (objp != (oc_object_t *)hhp) { + if ((objp->obj_key == key) && (objp->obj_group == group)) { + + /* Cache hit.*/ + return objp; + } + objp = objp->hash_next; + } + + return NULL; +} + +/** + * @brief Gets the least recently used object buffer from the LRU list. + * + * @param[out] ocp pointer to the @p objects_cache_t structure to be + * @return The pointer to the retrieved object. + * + * @notapi + */ +static oc_object_t *lru_get_last_s(objects_cache_t *ocp) { + oc_object_t *objp; + + while (true) { + /* Waiting for an object buffer to become available in the LRU.*/ + (void) chSemWaitS(&ocp->lru_sem); + + /* Now an object buffer is in the LRU for sure, taking it from the + LRU tail.*/ + objp = ocp->lru.lru_prev; + + chDbgAssert((objp->obj_flags & OC_FLAG_INLRU) == OC_FLAG_INLRU, + "not in LRU"); + chDbgAssert(chSemGetCounterI(&objp->obj_sem) == (cnt_t)1, + "semaphore counter not 1"); + + LRU_REMOVE(objp); + objp->obj_flags &= ~OC_FLAG_INLRU; + + /* Getting the object semaphore, we know there is no wait so + using the "fast" variant.*/ + chSemFastWaitI(&objp->obj_sem); + + /* If it is a buffer not needing (lazy) write then it can be used + right away.*/ + if ((objp->obj_flags & OC_FLAG_LAZYWRITE) == 0U) { + + /* Removing from hash table if required.*/ + if ((objp->obj_flags & OC_FLAG_INHASH) != 0U) { + HASH_REMOVE(objp); + } + + /* Removing all flags, it is "new" now.*/ + objp->obj_flags = 0U; + + return objp; + } + + + /* Out of critical section.*/ + chSysUnlock(); + + /* Invoking the writer asynchronously, it will release the buffer once it + is written. It is responsibility of the write function to release + the buffer.*/ + objp->obj_flags = OC_FLAG_INHASH | OC_FLAG_FORGET; + (void) ocp->writef(ocp, objp, true); + + /* Critical section enter again.*/ + chSysLock(); + } +} + +/*===========================================================================*/ +/* Module exported functions. */ +/*===========================================================================*/ + +/** + * @brief Initializes a @p objects_cache_t object. + * + * @param[out] ocp pointer to the @p objects_cache_t structure to be + * initialized + * @param[in] hashn number of elements in the hash table array, must be + * a power of two and not lower than @p objn + * @param[in] hashp pointer to the hash table as an array of + * @p oc_hash_header_t + * @param[in] objn number of elements in the objects table array + * @param[in] objsz size of elements in the objects table array, the + * minimum value is sizeof (oc_object_t). + * @param[in] objvp pointer to the hash objects as an array of structures + * starting with an @p oc_object_t + * @param[in] readf pointer to an object reader function + * @param[in] writef pointer to an object writer function + * + * @init + */ +void chCacheObjectInit(objects_cache_t *ocp, + ucnt_t hashn, + oc_hash_header_t *hashp, + ucnt_t objn, + size_t objsz, + void *objvp, + oc_readf_t readf, + oc_writef_t writef) { + + chDbgCheck((ocp != NULL) && (hashp != NULL) && (objvp != NULL) && + ((hashn & (hashn - (ucnt_t)1)) == (ucnt_t)0) && + (objn > (ucnt_t)0) && (hashn >= objn) && + (objsz >= sizeof (oc_object_t)) && + ((objsz & (PORT_NATURAL_ALIGN - 1U)) == 0U)); + + chSemObjectInit(&ocp->cache_sem, (cnt_t)1); + chSemObjectInit(&ocp->lru_sem, (cnt_t)objn); + ocp->hashn = hashn; + ocp->hashp = hashp; + ocp->objn = objn; + ocp->objvp = objvp; + ocp->readf = readf; + ocp->writef = writef; + ocp->lru.hash_next = NULL; + ocp->lru.hash_prev = NULL; + ocp->lru.lru_next = (oc_object_t *)&ocp->lru; + ocp->lru.lru_prev = (oc_object_t *)&ocp->lru; + + /* Hash headers initialization.*/ + do { + hashp->hash_next = (oc_object_t *)hashp; + hashp->hash_prev = (oc_object_t *)hashp; + hashp++; + } while (hashp < &ocp->hashp[ocp->hashn]); + + /* Object headers initialization.*/ + do { + oc_object_t *objp = (oc_object_t *)objvp; + + chSemObjectInit(&objp->obj_sem, (cnt_t)1); + LRU_INSERT_HEAD(ocp, objp); + objp->obj_group = 0U; + objp->obj_key = 0U; + objp->obj_flags = OC_FLAG_INLRU; + objp->dptr = NULL; + objvp = (void *)((uint8_t *)objvp + objsz); + objn--; + } while (objn > (ucnt_t)0); +} + +/** + * @brief Retrieves an object from the cache. + * @note If the object is not in cache then the returned object is marked + * as @p OC_FLAG_NOTSYNC meaning that its data contains garbage and + * must be initialized. + * + * @param[in] ocp pointer to the @p objects_cache_t structure + * @param[in] group object group identifier + * @param[in] key object identifier within the group + * @return The pointer to the retrieved object. + * + * @api + */ +oc_object_t *chCacheGetObject(objects_cache_t *ocp, + uint32_t group, + uint32_t key) { + oc_object_t *objp; + + /* Critical section enter, the hash check operation is fast.*/ + chSysLock(); + + /* Checking the cache for a hit.*/ + objp = hash_get_s(ocp, group, key); + if (objp != NULL) { + + chDbgAssert((objp->obj_flags & OC_FLAG_INHASH) == OC_FLAG_INHASH, + "not in hash"); + + /* Cache hit, checking if the buffer is owned by some + other thread.*/ + if (chSemGetCounterI(&objp->obj_sem) > (cnt_t)0) { + /* Not owned case, it is in the LRU list.*/ + + chDbgAssert((objp->obj_flags & OC_FLAG_INLRU) == OC_FLAG_INLRU, + "not in LRU"); + + /* Removing the object from LRU, now it is "owned".*/ + LRU_REMOVE(objp); + objp->obj_flags &= ~OC_FLAG_INLRU; + + /* Getting the object semaphore, we know there is no wait so + using the "fast" variant.*/ + chSemFastWaitI(&objp->obj_sem); + } + else { + /* Owned case, some other thread is playing with this object, we + need to wait.*/ + + chDbgAssert((objp->obj_flags & OC_FLAG_INLRU) == 0U, "in LRU"); + + /* Waiting on the buffer semaphore.*/ + (void) chSemWaitS(&objp->obj_sem); + } + } + else { + /* Cache miss, getting an object buffer from the LRU list.*/ + objp = lru_get_last_s(ocp); + + /* Naming this object and publishing it in the hash table.*/ + objp->obj_group = group; + objp->obj_key = key; + objp->obj_flags = OC_FLAG_INHASH | OC_FLAG_NOTSYNC; + HASH_INSERT(ocp, objp, group, key); + } + + /* Out of critical section and returning the object.*/ + chSysUnlock(); + + return objp; +} + +/** + * @brief Releases an object into the cache. + * @note This function gives a meaning to the following flags: + * - @p OC_FLAG_INLRU must be cleared. + * - @p OC_FLAG_INHASH must be set. + * - @p OC_FLAG_SHARED must be cleared. + * - @p OC_FLAG_NOTSYNC invalidates the object and queues it on + * the LRU tail. + * - @p OC_FLAG_LAZYWRITE is ignored and kept, a write will occur + * when the object is removed from the LRU list (lazy write). + * . + * + * @param[in] ocp pointer to the @p objects_cache_t structure + * @param[in] objp pointer to the @p oc_object_t structure + * + * @iclass + */ +void chCacheReleaseObjectI(objects_cache_t *ocp, + oc_object_t *objp) { + + /* Checking initial conditions of the object to be released.*/ + chDbgAssert((objp->obj_flags & (OC_FLAG_INLRU | + OC_FLAG_INHASH | + OC_FLAG_SHARED)) == OC_FLAG_INHASH, + "invalid object state"); + chDbgAssert(chSemGetCounterI(&objp->obj_sem) <= (cnt_t)0, + "semaphore counter greater than 0"); + + /* If some thread is waiting for this specific buffer then it is + handed directly without going through the LRU.*/ + if (chSemGetCounterI(&objp->obj_sem) < (cnt_t)0) { + /* Clearing all flags except those that are still meaningful, note, + OC_FLAG_NOTSYNC and OC_FLAG_LAZYWRITE are passed, the other thread + will handle them.*/ + objp->obj_flags &= OC_FLAG_INHASH | OC_FLAG_NOTSYNC | OC_FLAG_LAZYWRITE; + chSemSignalI(&objp->obj_sem); + return; + } + + /* If the object specifies OC_FLAG_NOTSYNC then it must be invalidated + and removed from the hash table.*/ + if ((objp->obj_flags & OC_FLAG_NOTSYNC) != 0U) { + HASH_REMOVE(objp); + LRU_INSERT_TAIL(ocp, objp); + objp->obj_group = 0U; + objp->obj_key = 0U; + objp->obj_flags = OC_FLAG_INLRU; + } + else { + /* LRU insertion point depends on the OC_FLAG_FORGET flag.*/ + if ((objp->obj_flags & OC_FLAG_FORGET) == 0U) { + /* Placing it on head.*/ + LRU_INSERT_HEAD(ocp, objp); + } + else { + /* Low priority data, placing it on tail.*/ + LRU_INSERT_TAIL(ocp, objp); + } + objp->obj_flags &= OC_FLAG_INHASH | OC_FLAG_LAZYWRITE; + objp->obj_flags |= OC_FLAG_INLRU; + } + + /* Increasing the LRU counter semaphore.*/ + chSemSignalI(&ocp->lru_sem); + + /* Releasing the object, we know there are no threads waiting so + using the "fast" signal variant.*/ + chSemFastSignalI(&objp->obj_sem); +} + +/** + * @brief Reads object data from the storage. + * @note In case of asynchronous operation an error condition is not + * reported by this function. + * + * @param[in] ocp pointer to the @p objects_cache_t structure + * @param[in] objp pointer to the @p oc_object_t structure + * @param[in] async requests an asynchronous operation if supported, the + * function is then responsible for releasing the + * object + * @return The operation status. In case of asynchronous + * operation @p false is always returned. + * @retval false if the operation succeeded. + * @retval true if the synchronous read operation failed. + * + * @api + */ +bool chCacheReadObject(objects_cache_t *ocp, + oc_object_t *objp, + bool async) { + + /* Marking it as OC_FLAG_NOTSYNC because the read operation is going + to corrupt it in case of failure. It is responsibility of the read + implementation to clear it if the operation succeeds.*/ + objp->obj_flags |= OC_FLAG_NOTSYNC; + + return ocp->readf(ocp, objp, async); +} + +/** + * @brief Writes the object data back to storage. + * @note In case of asynchronous operation an error condition is not + * reported by this function. + * + * @param[in] ocp pointer to the @p objects_cache_t structure + * @param[in] objp pointer to the @p oc_object_t structure + * @param[in] async requests an asynchronous operation if supported, the + * function is then responsible for releasing the + * object + * @return The operation status. In case of asynchronous + * operation @p false is always returned. + * @retval false if the operation succeeded. + * @retval true if the synchronous write operation failed. + * + * @api + */ +bool chCacheWriteObject(objects_cache_t *ocp, + oc_object_t *objp, + bool async) { + + /* Resetting the OC_FLAG_LAZYWRITE flag in order to prevent multiple + writes.*/ + objp->obj_flags &= ~OC_FLAG_LAZYWRITE; + + return ocp->writef(ocp, objp, async); +} + +#endif /* CH_CFG_USE_OBJ_CACHES == TRUE */ + +/** @} */ -- cgit v1.2.3