Modifying bit array locking behavior
Folks,
At the current time, bit arrays (see sys/bitarray.h and lib/os/bitarray.c for implementation) utilize a spin-lock to protect the contents from other execution contexts. As a bit array is a basic data structure that does not always need locking protection, I would like to hoist that locking out of the bit array routines and have that done by the caller (as is the case for other data types such as linked lists). This would change the behavior and semantics of bit arrays from their current paradigm, and would likely have some impacts beyond what I currently know about.
As I understand things, the in-tree use of bit arrays is currently confined to memory blocks (sys/mem_blocks.h and kernel/mem_blocks.c). Such a locking change would naturally impact memory block implementation as the locking would be hoisted out from bit arrays into the memory block routines that call the bit array routines. Out-of-tree use is an unknown, and it is reasonable to assume that there are projects that would be affected by this. To what extent that would be the case—I do not know. And there may be challenges to getting the word out about the behavior change, but as bit-arrays were introduced in April 2021 I would guess that their adoption would not be too widespread as to make it too much of a burden.
Thoughts? Comments?
Peter Mitsis
Minor correction … I found a couple other places in-tree where we use bit arrays. These are in cmsis_thread.c and kernel/mmu.c. Assuming that this locking proposal goes forward, then those two files would also be impacted.
Peter Mitsis
Sent: Monday, July 4, 2022 9:43 AM
To: devel@...
Subject: [Zephyr-devel] Modifying bit array locking behavior
Folks,
At the current time, bit arrays (see sys/bitarray.h and lib/os/bitarray.c for implementation) utilize a spin-lock to protect the contents from other execution contexts. As a bit array is a basic data structure that does not always need locking protection, I would like to hoist that locking out of the bit array routines and have that done by the caller (as is the case for other data types such as linked lists). This would change the behavior and semantics of bit arrays from their current paradigm, and would likely have some impacts beyond what I currently know about.
As I understand things, the in-tree use of bit arrays is currently confined to memory blocks (sys/mem_blocks.h and kernel/mem_blocks.c). Such a locking change would naturally impact memory block implementation as the locking would be hoisted out from bit arrays into the memory block routines that call the bit array routines. Out-of-tree use is an unknown, and it is reasonable to assume that there are projects that would be affected by this. To what extent that would be the case—I do not know. And there may be challenges to getting the word out about the behavior change, but as bit-arrays were introduced in April 2021 I would guess that their adoption would not be too widespread as to make it too much of a burden.
Thoughts? Comments?
Peter Mitsis
Hi Peter,
The bitarray API looks very similar to the atomic_t API and ATOMIC_DEFINE() macro (see sys/atomic.h). The main differences I see are the “region” APIs for bitarrays and the fact that bitarrays track the number of bits available in the object (through the dedicated struct). On most platforms (maybe even all currently supported?) the atomic APIs utilize architecture specific atomic CPU instructions and therefore do not require separate locking.
It seems to me like there’s a fair bit redundancy here, and probably one of these APIs could be merged into the other, or maybe bitarray could use ATOMIC_DEFINE() (plus a dynamically allocated variant of it) instead of its own construction of “bundles”?
Btw, is there an associated github issue on this topic? That might be a better place to continue the discussion.
Johan
From:
devel@... <devel@...> on behalf of Mitsis, Peter <peter.mitsis@...>
Date: Monday, 4. July 2022 at 17.16
To: Mitsis, Peter <peter.mitsis@...>, devel@... <devel@...>
Subject: Re: [Zephyr-devel] Modifying bit array locking behavior
Minor correction … I found a couple other places in-tree where we use bit arrays. These are in cmsis_thread.c and kernel/mmu.c. Assuming that this locking proposal goes forward, then those two files would also be impacted.
Peter Mitsis
Sent: Monday, July 4, 2022 9:43 AM
To: devel@...
Subject: [Zephyr-devel] Modifying bit array locking behavior
Folks,
At the current time, bit arrays (see sys/bitarray.h and lib/os/bitarray.c for implementation) utilize a spin-lock to protect the contents from other execution contexts. As a bit array is a basic data structure that does not always need locking protection, I would like to hoist that locking out of the bit array routines and have that done by the caller (as is the case for other data types such as linked lists). This would change the behavior and semantics of bit arrays from their current paradigm, and would likely have some impacts beyond what I currently know about.
As I understand things, the in-tree use of bit arrays is currently confined to memory blocks (sys/mem_blocks.h and kernel/mem_blocks.c). Such a locking change would naturally impact memory block implementation as the locking would be hoisted out from bit arrays into the memory block routines that call the bit array routines. Out-of-tree use is an unknown, and it is reasonable to assume that there are projects that would be affected by this. To what extent that would be the case—I do not know. And there may be challenges to getting the word out about the behavior change, but as bit-arrays were introduced in April 2021 I would guess that their adoption would not be too widespread as to make it too much of a burden.
Thoughts? Comments?
Peter Mitsis