From 6733466adf26030f781c2779747472150238cadd Mon Sep 17 00:00:00 2001 From: Amar Takhar Date: Sat, 16 Jan 2016 19:08:48 -0500 Subject: Split document into seperate files by section. --- porting/priority_bitmap.rst | 182 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 182 insertions(+) create mode 100644 porting/priority_bitmap.rst (limited to 'porting/priority_bitmap.rst') diff --git a/porting/priority_bitmap.rst b/porting/priority_bitmap.rst new file mode 100644 index 0000000..36c294b --- /dev/null +++ b/porting/priority_bitmap.rst @@ -0,0 +1,182 @@ +Priority Bitmap Manipulation +############################ + +Introduction +============ + +The RTEMS chain of ready tasks is implemented as an array of FIFOs with +each priority having its own FIFO. This makes it very efficient to +determine the first and last ready task at each priority. In addition, +blocking a task only requires appending the task to the end of the FIFO +for its priority rather than a lengthy search down a single chain of all +ready tasks. This works extremely well except for one problem. When the +currently executing task blocks, there may be no easy way to determine +what is the next most important ready task. If the blocking task was the +only ready task at its priority, then RTEMS must search all of the FIFOs +in the ready chain to determine the highest priority with a ready task. + +RTEMS uses a bitmap array to efficiently solve this problem. The state of +each bit in the priority map bit array indicates whether or not there is a +ready task at that priority. The bit array can be efficiently searched to +determine the highest priority ready task. This family of data type and +routines is used to maintain and search the bit map array. + +When manipulating the bitmap array, RTEMS internally divides the +8 bits of the task priority into "major" and "minor" components. +The most significant 4 bits are the major component, while the least +significant are the minor component. The major component of a priority +value is used to determine which 16-bit wide entry in the``_Priority_Bit_map`` array is associated with this priority. +Each element in the ``_Priority_Bit_map`` array has a bit +in the ``_Priority_Major_bit_map`` associated with it. +That bit is cleared when all of the bits in a particular``_Priority_Bit_map`` array entry are zero. + +The minor component of a priority is used to determine +specifically which bit in ``_Priority_Bit_map[major]`` +indicates whether or not there is a ready to execute task +at the priority. + +_Priority_bit_map_Control Type +============================== + +The ``_Priority_Bit_map_Control`` type is the fundamental data type of the +priority bit map array used to determine which priorities have ready +tasks. This type may be either 16 or 32 bits wide although only the 16 +least significant bits will be used. The data type is based upon what is +the most efficient type for this CPU to manipulate. For example, some +CPUs have bit scan instructions that only operate on a particular size of +data. In this case, this type will probably be defined to work with this +instruction. + +Find First Bit Routine +====================== + +The _CPU_Bitfield_Find_first_bit routine sets _output to the bit number of +the first bit set in ``_value``. ``_value`` is of CPU dependent type``Priority_bit_map_Control``. A stub version of this routine is as follows: +.. code:: c + + #define _CPU_Bitfield_Find_first_bit( _value, _output ) \\ + { \\ + (_output) = 0; /* do something to prevent warnings \*/ \\ + } + +There are a number of variables in using a "find first bit" type +instruction. + +# What happens when run on a value of zero? + +# Bits may be numbered from MSB to LSB or vice-versa. + +# The numbering may be zero or one based. + +# The "find first bit" instruction may search from MSB or LSB. + +RTEMS guarantees that (1) will never happen so it is not a concern. +Cases (2),(3), (4) are handled by the macros _CPU_Priority_mask() and +_CPU_Priority_bits_index(). These three form a set of routines which must +logically operate together. Bits in the ``_value`` are set and cleared based +on masks built by CPU_Priority_mask(). The basic major and minor values +calculated by _Priority_Major() and _Priority_Minor() are "massaged" by +_CPU_Priority_bits_index() to properly range between the values returned +by the "find first bit" instruction. This makes it possible for +_Priority_Get_highest() to calculate the major and directly index into the +minor table. This mapping is necessary to ensure that 0 (a high priority +major/minor) is the first bit found. + +This entire "find first bit" and mapping process depends heavily on the +manner in which a priority is broken into a major and minor components +with the major being the 4 MSB of a priority and minor the 4 LSB. Thus (0 +<< 4) + 0 corresponds to priority 0 – the highest priority. And (15 << +4) + 14 corresponds to priority 254 – the next to the lowest priority. + +If your CPU does not have a "find first bit" instruction, then there are +ways to make do without it. Here are a handful of ways to implement this +in software: + +- a series of 16 bit test instructions + +- a "binary search using if’s" + +- the following algorithm based upon a 16 entry lookup table. In this pseudo-code, bit_set_table[16] has values which indicate the first bit set: + + .. code:: c + + _number = 0 if _value > 0x00ff + _value >>=8 + _number = 8; + if _value > 0x0000f + _value >=8 + _number += 4 + _number += bit_set_table[ _value ] + +The following illustrates how the CPU_USE_GENERIC_BITFIELD_CODE macro may +be so the port can use the generic implementation of this bitfield code. +This can be used temporarily during the porting process to avoid writing +these routines until the end. This results in a functional although lower +performance port. This is perfectly acceptable during development and +testing phases. +.. code:: c + + #define CPU_USE_GENERIC_BITFIELD_CODE TRUE + #define CPU_USE_GENERIC_BITFIELD_DATA TRUE + +Eventually, CPU specific implementations of these routines are usually +written since they dramatically impact the performance of blocking +operations. However they may take advantage of instructions which are not +available on all models in the CPU family. In this case, one might find +something like this stub example did: +.. code:: c + + #if (CPU_USE_GENERIC_BITFIELD_CODE == FALSE) + #define _CPU_Bitfield_Find_first_bit( _value, _output ) \\ + { \\ + (_output) = 0; /* do something to prevent warnings \*/ \\ + } + #endif + +Build Bit Field Mask +==================== + +The _CPU_Priority_Mask routine builds the mask that corresponds to the bit +fields searched by _CPU_Bitfield_Find_first_bit(). See the discussion of +that routine for more details. + +The following is a typical implementation when the +_CPU_Bitfield_Find_first_bit searches for the most significant bit set: +.. code:: c + + #if (CPU_USE_GENERIC_BITFIELD_CODE == FALSE) + #define _CPU_Priority_Mask( _bit_number ) \\ + ( 1 << (_bit_number) ) + #endif + +Bit Scan Support +================ + +The ``_CPU_Priority_bits_index`` routine translates the bit numbers +returned by ``_CPU_Bitfield_Find_first_bit()`` into something +suitable for use as a major or minor component of a priority. +The find first bit routine may number the bits in a +way that is difficult to map into the major and minor components +of the priority. For example, when finding the first bit set in +the value 0x8000, a CPU may indicate that bit 15 or 16 is set +based on whether the least significant bit is "zero" or "one". +Similarly, a CPU may only scan 32-bit values and consider the +most significant bit to be bit zero or one. In this case, this +would be bit 16 or 17. + +This routine allows that unwieldy form to be converted +into a normalized form that is easier to process and use +as an index. +.. code:: c + + #if (CPU_USE_GENERIC_BITFIELD_CODE == FALSE) + #define _CPU_Priority_bits_index( _priority ) \\ + (_priority) + #endif + +.. COMMENT: COPYRIGHT (c) 1988-2002. + +.. COMMENT: On-Line Applications Research Corporation (OAR). + +.. COMMENT: All rights reserved. + -- cgit v1.2.3