Use win32 singly linked list instead of LVGL linked list for fixing memory access conflict issues for win32drv.

[MouriNaruto]

This issue is reported by @SmartAnda.

Memory access conflicts occur when frequent keyboard navigation is performed due to LVGL's implementation does not thread safe.

So, use win32 singly linked list instead of LVGL linked list for solving the issue without preparing a modified version of LVGL linked list implementation and keeping the win32drv implementation as simple as possible.

Kenji Mouri

[kisvegabor]

Looks good, thank you!

[MaD70]

@kisvegabor I don't understand how this can work: at first I thought that the proposed patch was accepted by mistake, because the data structure in interlockedapi.h is a stack not a queue (InterlockedPopEntrySList and InterlockedPushEntrySList, used in the patch, removes/inserts an item from the front of a singly linked list).

Then I noticed that indeed the code that the patch replaced uses the lv_ll_t data structure in lv_ll.h as a stack (pushes and pops from head with _lv_ll_ins_head and _lv_ll_get_head) and not as a queue. So at least the name of the keyboard_queue variable is misleading, but I wonder what's the point of processing the sequence of keystrokes always starting from the last one and going backwards (stack).

[MouriNaruto]

@MaD70

I don't understand how this can work.

Because LVGL's linked list doesn't support thread safe. And win32drv uses separate window thread to process the window message. (Make main thread can have more time to do with LVGL's scheduler.)

So at least the name of the keyboard_queue variable is misleading

Not misleading, because it's preprocessed Win32's keyboard input queue.

Kenji Mouri

[MaD70]

Because LVGL's linked list doesn't support thread safe. And win32drv uses separate window thread to process the window message. (Make main thread can have more time to do with LVGL's scheduler.)

@MouriNaruto that's not the part that is not clear to me (I linked to interlockedapi.h, I understood perfectly that the patch was made to make treadsafe the processing of keys from keyboard).

Not misleading, because it's preprocessed Win32's keyboard input queue.

I see that the keys in keyboard_queue come from the Win32's keyboard input queue (the lv_win32_window_message_callback event handler with the classic switch to dispatch events like the case for WM_KEYDOWN and WM_KEYUP) but keyboard_queue itself is created and managed by LVGL, it's not the Win32's keyboard input queue. I'm asking why keyboard_queue is managed like a stack.

[MouriNaruto]

@MaD70

I'm asking why "keyboard_queue" is managed like a stack.

We have the "keyboard_mutex" to keep the input sequence. Every LVGL keyboard processing callback will lock via mutex first and drain out the stack which saves the input key buffer. (For each time LVGL keyboard processing reads, it is like the queue.) Choose stack because we don't want to use pure C (because LVGL is a project as pure C as possible) to implement the thread safe queue by ourselves which is not tested by history.

Note: I think it still can have some improvements for the current implementation. (It's non continuous locking state when reading via LVGL. Although the unlocked time at this case is really short.)

Kenji Mouri

[MaD70]

@MouriNaruto wrote:

For each time LVGL keyboard processing reads, it is like the queue.

Ok, I trust you on this (to understand why this is true I would have to study the library in much more detail, it's not at all apparent from a normal reading and that's why I asked).

Choose stack because we don't want to use pure C (because LVGL is a project as pure C as possible) to implement the thread safe queue by ourselves which is not tested by history.

I understand this, concurrency is notoriously difficult to implement correctly. I'm not aware of any current and widely used C implementation of a thread safe queue. UPDATE: apparently such an implementation exists in the liblfds library (a portable, license-free, lock-free data structure library written in C. ... Current users include AT&T, Red Hat and Xen. Documentation).

If the need arises, I would suggest the algorithms adopted by the Java library Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms: on this web page there is pseudo-code for the implementation and at this link there is an old C implementation (.tgz) (accessed from this page: High-Performance Synchronization for Shared-Memory Parallel Programs, the link is in the section Legacy Executables at Fast concurrent queue algorithms).

The implementation should be modernized to use C11 Atomic operations library, in particular CAS (Compare-And-Swap) in pseudo-code should be one of the atomic_compare_exchange of C11.