Plans for caching in v9

[niklasf]

Introduce the problem

It looks like the new built-in cache (src/misc/lv_cache_builtin.h) is meant to be used with a relatively low number of elements. It iterates over all entries to find a match.

The older src/misc/lv_lru.h hashes keys to place elements in buckets.

Suppose there is a use case for caching many small bits of information. Which cache should be used?

Examples and cases

• The bitmap cache for Tiny TTF may hold lots of entries.
• Tiny TTF may benefit from also caching glyph metrics (keyed by font + font size + unicode letter + next unicode letter).

Suggested solution

What's the plan for caching in v9? Is lv_lru legacy and everything should use lv_cache, and should the built-in cache be changed to better deal with large numbers of entries? Or is lv_cache meant for small numbers of potentially big entries (like draw buffers), and lv_lru remains to be used for other cases?

[kisvegabor]

We have discussed it with @XuNeo and @FASTSHIFT that we should have multiple cache instances each having its own internal behavior, aging, storage logic, search implementation, etc.

We can have a cache instance for all images and other for letters, and a third e.g. for SDL textures.

[W-Mai]

I thought about it and conceived a new cache framework.

API that may be used by the newly designed cache

lv_cache_t * lv_cache_create(lv_cache_class_t * cache_class,
                                size_t node_size, size_t max_size,
                                lv_cache_compare_cb_t compare_cb,
                                lv_cache_alloc_cb_t alloc_cb,
                                lv_cache_free_cb_t free_cb);

void * lv_cache_get(lv_cache_t * cache, const void * key, void * user_data);
void   lv_cache_reset(lv_cache_t * cache, const void * key, void * user_data);
void   lv_cache_clear(lv_cache_t * cache, void * user_data);
void   lv_cache_set_max_size(lv_cache_t * cache, size_t max_size, void * user_data);
size_t lv_cache_get_max_size(lv_cache_t * cache, void * user_data);
size_t lv_cache_get_size(lv_cache_t * cache, void * user_data);
size_t lv_cache_get_free_size(lv_cache_t * cache, void * user_data);

void   lv_cache_set_compare_cb(lv_cache_t * cache, lv_cache_compare_cb_t compare_cb, void * user_data);
void   lv_cache_set_alloc_cb(lv_cache_t * cache, lv_cache_alloc_cb_t alloc_cb, void * user_data);
void   lv_cache_set_free_cb(lv_cache_t * cache, lv_cache_free_cb_t free_cb, void * user_data);

1. When a submodule is initialized
2. First create a cache, provide the cache_class (lv_cache_class_t) and node size, maximum capacity, compare callback, alloc callback, free callback, and return lv_cache_t object on success.
3. Each submodule that needs to use cache generally has a context structure. At this time, we can put the cache object we created into this context structure.
4. When used in the submodule, you only need to call the three interfaces: lv_cache_get, lv_cache_reset and lv_cache_clear.

Structural definitions

struct _lv_cache_t;
struct _lv_cache_class_t;

typedef struct _lv_cache_t lv_cache_t;
typedef struct _lv_cache_class_t lv_cache_class_t;

typedef int8_t lv_cache_compare_res_t;
typedef bool (*lv_cache_alloc_cb_t)(void* node, void* user_data);
typedef void (*lv_cache_free_cb_t)(void* node, void* user_data);
typedef lv_cache_compare_res_t (*lv_cache_compare_cb_t)(const void* a, const void* b);

typedef void (*lv_cache_init_t)(lv_cache_t* cache);
typedef void* (*lv_cache_get_t)(lv_cache_t* cache, const void* key, void* user_data);
typedef void (*lv_cache_reset_t)(lv_cache_t* cache, const void* key, void* user_data);
typedef void (*lv_cache_clear_t)(lv_cache_t* cache, void* user_data);

struct _lv_cache_t {
    lv_cache_class_t * clz;

    size_t node_size;

    size_t max_size;
    size_t size;

    lv_cache_compare_cb_t compare_cb;
    lv_cache_alloc_cb_t alloc_cb;
    lv_cache_free_cb_t free_cb;
};

struct _lv_cache_class_t {
    lv_cache_init_t init_cb;

    lv_cache_get_t get_cb;
    lv_cache_reset_t reset_cb;
    lv_cache_clear_t clear_cb;
};

The construction process of the object (assuming there is a cache of rb_lru):

LV_ATTRIBUTE_EXTERN_DATA extern const lv_cache_class_t lv_lru_rb_class;

const lv_cache_class_t lv_lru_rb_class = {
    .init_cb = NULL,
    .get_cb = NULL,
    .reset_cb = NULL,
    .clear_cb = NULL
};

struct _lv_lru_rb_t {
    lv_cache_t cache;

    lv_rb_t rb;
    lv_ll_t ll;
};
typedef struct _lv_lru_rb_t lv_lru_rb_t;

1. Let lv_lru_rb_class_t inherit from lv_cache_calss_t and add other dependent members (rb, ll, ...) to your structure.
2. When lv_cache_create is called, fill in the information of lv_cache_t (various sizes and callbacks) inside lv_cache_create, and then pass the object to init function of lv_lru_rb_class_t
3. In the init function of lv_lru_rb_class_t, initialize the two members rb and ll (if there are others, also initialize) and pass the other information needed to rb and ll (various sizes and callbacks)

The principle of object use

1. When the three interfaces of lv_cache_get, lv_cache_reset and lv_cache_clear are called, the call is passed to the class of the lv_cache_t object of the interface corresponding to get and reset, clear function
2. When the class of lv_cache_t object calls get and other functions, selectively calls the alloc, free and cmp related callbacks provided by lv_cache_t object according to their own needs.

Information that users need to provide when using

1. Node size: the size of the node to be cached, which contains key and value
2. alloc callback: When calling lv_cache_get, if the node does not exist, the cache object manages the memory allocation by itself. When the memory is allocated, call the allocation callback function provided by the user and let the user fill the data into it. If the user decides that the current allocation fails, it returns false, the cache object frees the allocated memory, and lv_cache_get returns NULL at the same time.
3. free callback: When the cache node is eliminated, the release callback will be called. Users need to deal with their own additional allocated memory and other things. After the callback function ends, the cache node memory is controlled and recycled by the cache object.
4. compare callback: used to determine whether the current node satisfies the user's incoming key

How about this?

[niklasf]

Cool, I like the approach. Some questions for clarification:

1. Assuming allocation succeeds, is lv_cache_get() guaranteed to always make space for the latest item? The current lv_cache has a mechanism for returning results, even if the cache was full.
2. Having only compare_cb limits possible cache implementations to tree-based approaches. Hashmaps are an interesting alternative, but I believe that would require something like an additional hash_cb?
3. I guess node_size is the expected average node size? This would be sufficient for glyph caches. I am not sure how predictable texture caches are.
4. In typedef lv_cache_compare_res_t (*lv_cache_compare_cb_t)(const void* a, const void* b), are a and b nodes or keys? If they are keys, how does the cache implementation keep a copy of the keys?

[W-Mai]

Thank you for your reply! Very good question!

1 . Assuming allocation succeeds, is lv_cache_get() guaranteed to always make space for the latest item? The current lv_cache has a mechanism for returning results, even if the cache was full. 3 . I guess node_size is the expected average node size? This would be sufficient for glyph caches. I am not sure how predictable texture caches are. 4 . In typedef lv_cache_compare_res_t (*lv_cache_compare_cb_t)(const void* a, const void* b), are a and b nodes or keys? If they are keys, how does the cache implementation keep a copy of the keys?

In fact, node_size refers to the size of a structure composed of key and value used as cache, and key and value exist in the same structure. If your key is temporarily assigned, you can copy the key again in alloc_cb and release the corresponding key in free_cb.

If the node size is uncertain, you can place the newly allocated memory in the alloc cb and place the allocated data in the node in the form of a pointer. Therefore, in response to the first question, there is currently no mechanism to ensure the use of temporary cache. If you really want to put it in, you need to release other nodes that meet the elimination algorithm.

2. Having only compare_cb limits possible cache implementations to tree-based approaches. Hashmaps are an interesting alternative, but I believe that would require something like an additional hash_cb?

I haven't considered this yet, and I need to think about how to make it appropriate.

[W-Mai]

void * lv_cache_get(lv_cache_t * cache, const void * key, void * user_data);

This API may be somewhat confusing, and maybe a better name is

void * lv_cache_get_or_create(lv_cache_t * cache, const void * key, void * user_data);

At the same time, it can support a simple cache query interface (which may not be needed) as shown below (change the definition of the get interface)

void * lv_cache_get(lv_cache_t * cache, const void * key, void * user_data);

typedef bool (*lv_cache_alloc_cb_t)(void* node, void* user_data);

The name of alloc_cb is not very good, which is easy to misunderstand, thinking that it must be alloc something.

I think query_cb or create_cb may be more appropriate.

[W-Mai]

@niklasf In fact, we had already realized a glyph caches in this pr https://github.com/lvgl/lvgl/pull/4669

It uses red black tree to store the cache entry, and the API is similar to the API this issue mentioned.

[kisvegabor]

Thanks for the summary. A few notes:

• We need to have a usage counter for the nodes. If there is a multi threading environment it can heppen that thread A is using an entry now, thread B interrupts it and wants to cache something, there is no space, and the entry used by thread A is dropped. We need to know that which entry is being used and do not drop it.
• Due to the same multi threading issues we need something like lv_cache_lock/unlock. Having a mutext in each API call is not enough as it might happen that we need to use multiple cache operation after each other and and it cannot happen that the entry is dropped in the meantime.
• We need to have a reference to the source of the cache. Let's say "img1.png" is used by by the PNG decoder and cached as an SDL texture too. When "img1.png" changes, we need to drop the related entries in all lv_cache_ts. It also means that lv_cache_ts needs to be added to linked list.
• What is the difference between reset and clear?
• What happens if the size to allocate is larger than max_size? The entry cannot be allocated, or we allocate it and also drop it immediately after it was used.
• I'm not sure about alloc_cb. The other option is if get or query returns NULL we allocate the data and call a cache_add(cache, key, value) function. It seems more flexible to as this way different kind of data can be allcate in the same lv_cache_t. It might be required if we use a single lv_cache_t for all image decoders (PNG, JPG, etc).

[W-Mai]

Good question!

I don't have more insights about multithreading. I'm not good at this😔. My current understanding is that it is for the same cache object, which can only be used by one thread at the same time. For example, when one thread applies for entry, another thread cannot apply for a new entry at the same time.

Regarding the use of sdl and the continuous use of the png decoder, @XuNeo gives a good solution that when the image cache is created, it will produce not only the data that the picture has been decoded, but also a self-increment id. Every time sdl needs to use the picture cache, go to the image cache to request whether the current id still exists. If it does not exist, the image cache of sdl will be invalid.

If the maximum of cache is exceeded, my current idea is that it cannot be used and LV_LOG_ERROR is issued.

Reset means invalidate an entry, and my name is not good. Clear can be invalidate_all

As for alloc_cb, I think this is the solution I have given at present to make the code more concise, which is equivalent to concentrating all the post-processing code after allocation (the same as free). As for the problem of using the same cache, maybe we can use the same cache object in lv_image_decoder_dsc_t.

[kisvegabor]

I don't have more insights about multithreading. I'm not good at this😔. My current understanding is that it is for the same cache object, which can only be used by one thread at the same time. For example, when one thread applies for entry, another thread cannot apply for a new entry at the same time.

There are 2 independent but threading related issues:

1. 2 thread are trying use the cache at the same time: the cache needs to be locked, else the concurrent access will mess it up
2. A entry cannot be dropped in a thread while an other thread is still using it. E.g. an image is drawn by core 1, core 2 cannot invalidate the entry used by core1.

Regarding the use of sdl and the continuous use of the png decoder, @XuNeo gives a good solution that when the image cache is created, it will produce not only the data that the picture has been decoded, but also a self-increment id. Every time sdl needs to use the picture cache, go to the image cache to request whether the current id still exists. If it does not exist, the image cache of sdl will be invalid.

Let me give you an other example: let's say TinyTTF uses Arial.ttf to create font_16 and font_32. If Arial.ttf changes/removed/etc, all the glyphs that are cached in font_16 and font_32 needs to dropped (can mean e.g. 200 entries).

In case of images, let's say "img1.png" is used in a SDL texture. No decoding was involved as SDL managed the image drawing by itself. However we are using SW render to draw "img1.png" to a canvas many times. It might be decoded many times, but the SDL texture is still valid. But once we change "img1.png", the texture needs to be dropped.

If the maximum of cache is exceeded, my current idea is that it cannot be used and LV_LOG_ERROR is issued.

In the current cache a temporary entry is created which is freed after use. I'm not sure which way is better. Both seems valid.

Reset means invalidate an entry, and my name is not good. Clear can be invalidate_all

What about drop instead of reset?

As for alloc_cb, I think this is the solution I have given at present to make the code more concise, which is equivalent to concentrating all the post-processing code after allocation (the same as free). As for the problem of using the same cache, maybe we can use the same cache object in lv_image_decoder_dsc_t.

Sorry, I got lost here :sweat_smile:

[W-Mai]

Let me give you an other example: let's say TinyTTF uses Arial.ttf to create font_16 and font_32. If Arial.ttf changes/removed/etc, all the glyphs that are cached in font_16 and font_32 needs to dropped (can mean e.g. 200 entries).

In case of images, let's say "img1.png" is used in a SDL texture. No decoding was involved as SDL managed the image drawing by itself. However we are using SW render to draw "img1.png" to a canvas many times. It might be decoded many times, but the SDL texture is still valid. But once we change "img1.png", the texture needs to be dropped.

In response to this problem, I think there are two solutions that can be dealt with at present.

1. Register the callback function. Each font that uses arial.ttf registers a "change callback function" with this arial.ttf. When there is any change in the file, notify each font that uses the file, and then notify them to drop the current entry. Of course, there will also be some problems:

   1. A new change interface needs to be added to the file system.
   2. The file system needs to maintain a callback list

2. Check whether arial.ttf is still effective wherever you use it. When using arial.ttf, use arial.ttf and his update datetime as the key of cache entry (or directly use lv_fs_file_t). Then when arial.ttf changes, which font's glyph needs to be used, immediately update the current glyph. We don't need to care about and drop all the cache entries immediately. We just need to drop and regenerate the cache entries when we use them.

   1. The change that needs to be made is that we need to check every time we use cache entry, but in fact we have been doing so.

Sorry, I got lost here 😅

Regarding alloc_cb or named create_cb, let me try to explain what it is and how to use it. Its main function is to automatically create data filled with cache entry according to the context provided by lv_cache_get_or_create after the cache entry is created.

In the above example of arial.ttf, if our arial.ttf file changes, we don't need to write too much code, we just need to call lv_cache_get_or_create, in lv_cache_get_or_create after finding that the key has changed, it will recreate the cache entry and automatically fill in the creation and filling data according to the context. And outdated data does not need our care. It will be automatically eliminated by the algorithm. We don't have to worry about the problem with cache entry because we ask for a new key every time.

Of course, there will be other unexpected situations. When we using lv_cache_get_or_create, the file has not changed, but there has been changes during the drawing process. I think this problem is unsolvable.

[XuNeo]

The requirement for cache now looks really complicated. However, from a user's perspective, the exposed API should be as simple as possible. Take a look at https://github.com/lvgl/lvgl/pull/4928/files, I propose APIs as below.

/**
 * Put data to cache
 * @param cache the cache instance
 * @param key   the pointer to the key, it's ok to use pointer as key, thus len is 4 typically. `key` is deep copied in cache module.
 * @param len   the length of the key
 * @param data  Pointer to the data to cache, transparent to cache module. We don't care length of data
 * @return      the cache entry, could be saved locally for later use.
 */

lv_cache_entry_t * lv_cache_put(lv_cache_t * cache, void * key, size_t len, void * data);

/**
 * Get data from cache, return NULL if not found
 */
lv_cache_entry_t * lv_cache_get(lv_cache_t * cache, void * key, size_t len);

As for image decoder, the key could be a path to image or a pointer to c-array image.

Edit: Differ with normal cache operation, we have to add lv_cache_release to say we have finished using the cache entry.

void lv_cache_release(lv_cache_t * cache, lv_cache_entry_t * entry);

[kisvegabor]

In response to this problem, I think there are two solutions that can be dealt with at present.

What is the data source (font or image) is stored in an array and there is no file system?

Sorry, I got lost here 😅

Regarding alloc_cb or named create_cb, let me try to explain what it is and how to use it. Its main function is to automatically create data filled with cache entry according to the context provided by lv_cache_get_or_create after the cache entry is created.

I understand now, thank you. My question above is related to this as well.

Are there any issues wit storing the src (pointer or path) independently of key and data? It seems the simplest solution to me.

[XuNeo]

Are there any issues wit storing the src (pointer or path) independently of key and data? It seems the simplest solution to me.

It involves upper logic to cache such as what is a source, where cache should only care about how to cache data and retrive data via key.

Image cache built on top of basic cache lib, has the knowledge of what is an image, either a pointer or a path.

[kisvegabor]

I see. it also makes sense to keep cache logic as simple as possible.

To put it really simple, how can we solve these problems?

• Images
  • We created a canvas
  • SDL draws it into a texture, and caches that texture
  • The canvas is updated
  • The related texture needs to dropped/ignored
• Fons
  • We created a font from Arial.ttf and we set the the size to 20px
  • We have used 'A', 'B', 'C' letters (3 entries in the cache)
  • Now we update the font to use Roboto.ttf
  • All 3 letters should be dropped/ignored

We can consider it as an upper layer in for images and fonts, but it seems like a generic problem affecting many parts of the library.

[W-Mai]

As far as this problem is concerned, the solution is to make canvas identifiable, such as adding a marker bit such as version, id, generation, etc. Every time operating the canvas, it will increase the value by 1.

In this way, you can take the id of canvas and the pointer of the canvas object itself as the key to determine whether the cavas has been invalidated.

[XuNeo]

As far as this problem is concerned, the solution is to make canvas identifiable, such as adding a marker bit such as version, id, generation, etc. Every time operating the canvas, it will increase the value by 1.

In this way, you can take the id of canvas and the pointer of the canvas object itself as the key to determine whether the cavas has been invalidated.

There's only one field to add, generation, which is used to describe if the cached data has changed or not.

So for SDL texture, when it gets a entry from image cache in order to draw image, it should record the image cache entry. The next time call to SDL draw image, it should firstly get image cache again and compare with stored cache entry to check if it's changed or not. Since entry pointer is unique, compare the entry pointer is enough to detect if data changed. Thus the generation field in cache entry can also be eliminated.

To invalidate cache, it simply check if the reference count is zero, release it immediately if so. Otherwise, it means cache entry is used by other threads, thus can only be detached from tree(or has map). When it's released, check reference count again and do free operation.

[W-Mai]

As far as this problem is concerned, the solution is to make canvas identifiable, such as adding a marker bit such as version, id, generation, etc. Every time operating the canvas, it will increase the value by 1. In this way, you can take the id of canvas and the pointer of the canvas object itself as the key to determine whether the cavas has been invalidated.

There's only one field to add, generation, which is used to describe if the cached data has changed or not.

So for SDL texture, when it gets a entry from image cache in order to draw image, it should record the image cache entry. The next time call to SDL draw image, it should firstly get image cache again and compare with stored cache entry to check if it's changed or not. Since entry pointer is unique, compare the entry pointer is enough to detect if data changed. Thus the generation field in cache entry can also be eliminated.

To invalidate cache, it simply check if the reference count is zero, release it immediately if so. Otherwise, it means cache entry is used by other threads, thus can only be detached from tree(or has map). When it's released, check reference count again and do free operation.

one problem, in this way, you can't tell whether the canvas was changed.

[XuNeo]

one problem, in this way, you can't tell whether the canvas was changed.

Canvas will invalidate image cache, thus a new image cache entry will return to SDL when it draws this image.

[kisvegabor]

So for SDL texture, when it gets a entry from image cache in order to draw image, it should record the image cache entry.

What if the entry recorded in the Texture is invalidated and freed in the meantime. In this case it will be wild pointer.

[XuNeo]

In this case it will be wild pointer

Yes, that why we need to check if it's wild before using it every time to draw image or front from their cache. Checking if it's wild is simply lv_cache_get(key) again and compare locally save pointer.

[kisvegabor]

Since entry pointer is unique, compare the entry pointer is enough to detect if data changed. Thus the generation field in cache entry can also be eliminated.

Without the generation field how can we see if "my_image.png" has changed? Its key will be same as before the change, so the same entry will be returned.

Let's assume it has a different key and it will result in a different cache entry. Shall with just compare the address of the saved and returned entry or the values too?

• Address only: If the saved entry was freed, we cannot assume much. It can happen that by chance the returned entry was allocated at the exact same address.
• Value: As there can be any data pointed by the wild pointer and comparison is not predictable.

[XuNeo]

I see your points about chances allocating same address.

Its key will be same as before the change, so the same entry will be returned.

If image has been changed, lv_cache_invalidate is called to mark entry as deleted or deferred to delete. The next time SDL draw unit call lv_cache_get(key) with same key my_image.png , it returns a different newly alloced entry, with new generation value.

Shall with just compare address of the saved and returned entry or the values too?

So we should compare if the returned address is same and generation is same. SDL draw unit needs to save both pointer to entry and its generation value.

[kisvegabor]

So if the address are different, the data is different for sure. If the address is the same the very unlikely event of allocating to the same address happened.

What if

• the saved entry with generation=0 is marked as to-be-deleted, a lot of time passes and it's really deleted
• a new entry is allocated with the default generation=0

---

It's not fully clear to me how the generation will be incremented if "my_image.png" is asynchronously changed on the file system.

[XuNeo]

It's not fully clear to me how the generation will be incremented if "my_image.png" is asynchronously changed on the file system.

The 32bit at least generation will be increased whenever a new entry alloced, not only for my_image.png but a global value for each cache instance. It's only to be unique and no need to be continuous.

When generation wraps to 0 again, it does have possibility for same image have two entries having same generation. But I think the chance is really low. The end solution is to generate a hash of image data as generation, but it's probably too much.

The API needs to be revised for better understanding.

lv_cache_entry_t * lv_cache_add(lv_cache_t * cache, void * key, size_t len, void * data);
void lv_cache_remove(lv_cache_t * cache, lv_cache_entry_t * entry);

lv_cache_entry_t * lv_cache_acquire(lv_cache_t * cache, void * key, size_t len);
void lv_cache_release(lv_cache_t * cache, lv_cache_entry_t * entry);

[kisvegabor]

I see. Let's examine the prevous example in light of that:

Images

• We created a canvas
• SDL draws it into a texture, and caches that texture
• The canvas is updated
• The related texture needs to dropped/ignored

I'm not sure if generation is unique in each lv_cache_t or really global. Let's assume really global. I think this what will happen:

• let's say generation=100 now
• the canvas is cached in lv_cache_t sdl_cache with generation=100 and now generation=101, Let's say the key is 20
• the canvas is updated, key is still 20
• what will tell to lv_cache_acquire in sdl_cache that the canvas has been changed? For the same key it can still return the same entry. We cannot invalidate it either, because in the cache entry we just cache the data which can be anything, maybe not original source. Actually it's an SDL_Texture and an lv_image_draw_dsc in this case from which we don't know directly what was the original image.

Probably your idea is working and I'm just missing something.

[xlbao123]

I would like to share some suggestions regarding the cache module:

1. We need a mutex to prevent multi-threading issues (can be disabled for single-threaded applications). Additionally, the public API of this module should only use key as the index for entries. This way, there is no need to worry about the cache being released during the call.

2. The cache is divided into three levels: pool -> block -> entry.

   • Create an image pool where each block has only one entry. (it can be expanded, for example, when combining multiple small images into one large image, a block can describe the large image, and entries can describe the coordinates and size of the small images on the large)
   • Create a font pool, with each font instance using an independent block. For example, the same noto.ttf font must have two different blocks in the font pool for font sizes 32 and 40.
   • Possible other pools: a file memory pool for caching files, a text shaper pool for caching harfbuzz glyphs.
   • Support creating custom pools.

3. Use reference counting for management.

4. Use an independent key-value structured map to manage entries. In my experience, rbtree is efficient enough.

5. Cache mechanisms:

   • Support various mechanisms such as lru, mem fail, etc. Each pool can choose its own mechanism(determined by flags). For example, the image pool may have limits on total size and individual image size.
   • Blocks need to distinguish whether they are read-only, such as in scenarios where resources are placed on NOR flash.

6. Regarding changes to resources in the file system while there are also within the cache, I think this is a consideration for product development. For example, he can monitor changes to files or directories on the file system through the os apis and call the cache module's api to clear the cache corresponding to a specific pool and entry key. In my usage, since resource changes are infrequent, I only need to monitor the resource directory and then clean all pools.

7. Regarding memory allocation and release for the data corresponding to each entry, I am not sure if lvgl has corresponding apis at the draw layer (or render layer) for allocating surface memory. The creation of entries needs to provide two interfaces: one is to internally call the draw->alloc_surface, and the other is to create an entry by passing in already allocated surface memory (this is more convenient for many image decoding libraries). The reason for using the draw layer's allocation interface is that each GPU has its own memory requirements (such as alignment, stride, etc.), and the entry's surface itself is intended for direct rendering by the draw layer.

[kisvegabor]

@xlbao123 Thank you for jumping in!

Regarding changes to resources in the file system while there are also within the cache, I think this is a consideration for product development. For example, he can monitor changes to files or directories on the file system through the os apis and call the cache module's api to clear the cache corresponding to a specific pool and entry key. In my usage, since resource changes are infrequent, I only need to monitor the resource directory and then clean all pools.

My problem here is that from the user's or developer's point of view the data from which the key is generated might not be available. Simple example

key1 = hash("my_image.png")
key2 = hash("my_image.png" + rotation = 30°)
key3 = hash("my_image.png" + rotation = 40° + scale=120%)
key4 = hash("my_image.png" + rotation = 50° + recolor(red) + recolor intensity(20%) + clipped(area, radius))

How can the user invalidate all entries related to "my_image.png"?

[xlbao123]

@xlbao123 Thank you for jumping in!

Regarding changes to resources in the file system while there are also within the cache, I think this is a consideration for product development. For example, he can monitor changes to files or directories on the file system through the os apis and call the cache module's api to clear the cache corresponding to a specific pool and entry key. In my usage, since resource changes are infrequent, I only need to monitor the resource directory and then clean all pools.

My problem here is that from the user's or developer's point of view the data from which the key is generated might not be available. Simple example

key1 = hash("my_image.png")
key2 = hash("my_image.png" + rotation = 30°)
key3 = hash("my_image.png" + rotation = 40° + scale=120%)
key4 = hash("my_image.png" + rotation = 50° + recolor(red) + recolor intensity(20%) + clipped(area, radius))

How can the user invalidate all entries related to "my_image.png"?

My first idea is:

key1 = hash("my_image.png")
key2 = hash("my_image.png_r30")
key3 = hash("my_image.png_r40_s120")
...

This way, when it's necessary to clear "my_image.png," it can be cleared by prefix.

Another idea is: Images reside in the image pool, and operations like rotation/scaling/coloring/clipping do not require separate caching (in 3D scenarios, a shader pool might be needed). For performance considerations, caching mechanism should be provided for the entire widget, so there can be a widget pool. Thus, if key1 changes, it would trigger the corresponding widget to be re-rendered, consequently updating the corresponding entry in the widget pool.

[XuNeo]

How can the user invalidate all entries related to "my_image.png"?

User can simply invalidate the cache using "my_image.png". Whoever have used the data, should always firstly lv_cache_acquire("my_image.png"), where it will find out the "my_image.png" is missing, thus get an NULL entry. Or it gets a new entry but with different generation.

[XuNeo]

I have prepared a draft that discussed in our team. API parameters need further tweaking, but we have considered some corner cases like multiple-threading etc.

Let's focus on how the cache is used.

Design Considerations

• Multiple instance

The cache is designed to work for both image and font, and any other modules like SDL texture. Each of them should operate on their own cache

• Multiple backends

Currently the cache data should be able stored in a linear tree, or a RB tree. Thus needs multiple backends.

• Multiple aging method

For image cache, we may use LRU aging algorithm, others may not. It should be a runtime configuration per cache instance

• Reference count

We only return a pointer to data for use in draw unit and other consumers, thus need reference count to check if the data is still being used

• Multiple threads

The cache entry returned could be used by other threads

APIs and Functionality

typedef enum _lv_cache_backend_t {
    LV_CACHE_BACKEND_RB = 0, /*RB tree as backend*/
    LV_CACHE_BACKEND_HASHMAP, /*Hashmap as backend*/
} lv_cache_backend_t;

typedef enum _lv_cache_aging_t {
    LV_CACHE_AGING_LRU = 0,
} lv_cache_aging_t;

typedef enum _lv_cache_entry_t {
    uint32_t generation;    /*Generation of associated data*/
    uint32_t ref_count;
    void * key;             /*Deep copy of user's key*/
    uint32_t key_len;
    const void * data;      /*Transparent user's data*/
    uint32_t data_len;      /*Data length*/
    uint32_t weight;        /*May used by aging algorithm*/
} lv_cache_entry_t;

typedef enum _lv_cache_t {
    lv_cache_backend_t backend;
    lv_cache_aging_t aging;
    uint32_t generation; /*A global self-increase unique ID*/
    uint32_t capacity;
} lv_cache_t;

/*Create and destroy cache instances*/
lv_cache_t * lv_cache_create(lv_cache_backend_t backend, lv_cache_aging_t aging, uint32_t capacity);
void lv_cache_destroy(lv_cache_t * cache);

/*Add data to cache and invalidate data from cache*/
lv_cache_entry_t * lv_cache_add(lv_cache_t * cache, const void * key, size_t key_len,
                                void * data, uint32_t data_len, uint32_t weight);
void lv_cache_invalidate(lv_cache_t * cache, const void * key, size_t key_len);

/*Get data from cache and hold it*/
lv_cache_entry_t * lv_cache_acquire(lv_cache_t * cache, const void * key, size_t key_len);
/*Return data back to cache*/
void lv_cache_release(lv_cache_t * cache, lv_cache_entry_t * entry);

Use Cases of Image Cache

1. Image decoder open and decode file, put decoded data to cache, and next call to decoder_open will try cache firstly.

lv_result_t lv_bin_decoder_open(lv_image_decoder_t * decoder, lv_image_decoder_dsc_t * dsc)
{
    const void * key = dsc->src;
    uint32_t key_len = dsc->src_typ == TYPE_FILE ? strlen(key) : sizeof(void *);
    lv_cache_entry_t *entry = lv_cache_acquire(imgcache, key, key_len);
    if (entry) {
        /*If the data is in cache, use it directly*/
        dsc->decoded = entry->data;
        return LV_RESULT_OK;
    }

    void * data = decode_image(dsc);
    if (data) {
        /*Add data to cache, the global `generation` is increased and 
         * assigned to this entry */
        entry = lv_cache_add(imgcache, key, key_len, data, data_len);
        dsc->decoded = entry->data;
        dsc->generation = entry->generation; /*Remember generation of data we used*/
        lv_cache_acquire(imgcache, key, key_len); /*Increase reference count*/
        return LV_RESULT_OK;
    }
}

void lv_bin_decoder_close(lv_image_decoder_t * decoder, lv_image_decoder_dsc_t * dsc)
{
    if(dsc->cache_entry) {
        lv_cache_release(imgcache, dsc->cache_entry);
    }
}

void when_image_changes(void *src)
{
    /**
     * Invalidate cache will check the reference count, if it's zero, then the
     * entry is completely removed from cache.
     *
    * If the reference count is non - zero,
    * it means the resource is currently being used. After invalidation,
    * the entry is moved to the deferred_delete list.
    * When the reference count reaches zero, lv_cache_release will find 
    * and remove the entry from the list.
    */
    lv_cache_invalidate(imgcache, src);
}

2. Interaction between multiple cache instances.

SDL draw unit will cache draw result. SDL texture, the draw result, may contains images and fonts that from other cache instances. So whenever a cache entry is acquired, always compare if generation meets our local stored generation`. Otherwise, it's means data has been changed.

/*For SDL draw image task*/
void sdl_draw_image(lv_draw_image_dsc_t *dsc)
{
    const void * key = dsc->src;
    uint32_t key_len = dsc->src_typ == TYPE_FILE ? strlen(key) : sizeof(void *);
    lv_cache_entry_t *entry = lv_cache_acquire(imgcache, key, key_len);
    if (entry && entry->generation == dsc->generation) {
        /*If the data is in cache, and the data has not changed.*/
        
        /*Note: we have to check generation because the cache entry has been released
         * after draw finished.*/
        lv_cache_entry_t * sdl = lv_cache_acquire(sdlcache, sdlkey, sdl_key_len);
        SDL_Texture * textur = sdl->data;
        /*Use the texture directly.*/
        lv_cache_release(sdlcacle, sdl);
        lv_cache_release(entry);
        return LV_RESULT_OK;
    }
    
    /*Otherwise, the data is not in image cache, or the image itself has been changed.*/
    /*Draw again*/
    lv_cache_release(entry);
}

3. Buffer manually allocated by user and used as image source

We forbid user manually allocate a random buffer. But instead the image cache will provide below APIs.

lv_draw_buf_t * lv_image_cache_alloc(uint32_t w, uint32_t h, lv_color_format_t cf, uint32_t stride)
void lv_image_cache_free(lv_draw_buf_t *);

lv_image_cache_alloc will firstly create draw buffer and add to cache, increase reference count and then return to user. lv_image_cache_free will only release the cache entry. Memory will only be free'd when reference count becomes '0'.