Real-Time OS Features

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

/* Static Allocation Patterns for Real-Time Systems */
 
#include <stdint.h>
#include <stdbool.h>
 
/* ============================================
 * Pattern 1: Compile-Time Static Arrays
 * ============================================ */
 
/* All buffers allocated at compile time */
#define MAX_SENSOR_READINGS     1000
#define MAX_NETWORK_PACKETS     64
#define MAX_LOG_ENTRIES         256
 
/* Static arrays - no allocation ever */
static sensor_reading_t sensor_buffer[MAX_SENSOR_READINGS];
static network_packet_t packet_buffer[MAX_NETWORK_PACKETS];
static log_entry_t log_buffer[MAX_LOG_ENTRIES];
 
/* Circular buffer indices */
static volatile uint32_t sensor_head = 0, sensor_tail = 0;
 
/* Add reading - O(1), no allocation */
bool add_sensor_reading(const sensor_reading_t *reading) {
    uint32_t next_head = (sensor_head + 1) % MAX_SENSOR_READINGS;
    
    if (next_head == sensor_tail) {
        return false;  /* Buffer full - deterministic failure */
    }
    
    sensor_buffer[sensor_head] = *reading;
    sensor_head = next_head;
    return true;
}
 
/* ============================================
 * Pattern 2: Pre-allocated Task Stacks
 * ============================================ */
 
#define NUM_TASKS           8
#define TASK_STACK_SIZE     4096
 
/* Static stack space for all tasks */
static uint8_t task_stacks[NUM_TASKS][TASK_STACK_SIZE]
    __attribute__((aligned(8)));
 
/* Static TCB structures */
static task_control_block_t task_tcbs[NUM_TASKS];
 
/* Initialize task with static resources */
void init_task(uint32_t task_id, void (*entry)(void*), void *arg) {
    if (task_id >= NUM_TASKS) {
        return;  /* Invalid task ID */
    }
    
    task_control_block_t *tcb = &task_tcbs[task_id];
    
    /* Use pre-allocated stack */
    tcb->stack_base = task_stacks[task_id];
    tcb->stack_size = TASK_STACK_SIZE;
    tcb->stack_ptr = &task_stacks[task_id][TASK_STACK_SIZE - 64];
    
    /* Set up initial context */
    setup_initial_context(tcb, entry, arg);
}
 
/* ============================================
 * Pattern 3: Message Pools with Static Storage
 * ============================================ */
 
#define MAX_MESSAGES        32
#define MESSAGE_SIZE        128
 
typedef struct {
    uint8_t data[MESSAGE_SIZE];
    bool in_use;
} static_message_t;
 
static static_message_t message_pool[MAX_MESSAGES];
static spinlock_t pool_lock;
 
/* Allocate message - O(n) worst case, but N is fixed and small */
uint8_t *alloc_message(void) {
    spin_lock(&pool_lock);
    
    for (int i = 0; i < MAX_MESSAGES; i++) {
        if (!message_pool[i].in_use) {
            message_pool[i].in_use = true;
            spin_unlock(&pool_lock);
            return message_pool[i].data;
        }
    }
    
    spin_unlock(&pool_lock);
    return NULL;  /* Pool exhausted - deterministic */
}
 
/* Free message - O(1) */
void free_message(uint8_t *msg) {
    /* Calculate pool index from pointer */
    ptrdiff_t offset = msg - message_pool[0].data;
    uint32_t index = offset / sizeof(static_message_t);
    
    if (index < MAX_MESSAGES) {
        spin_lock(&pool_lock);
        message_pool[index].in_use = false;
        spin_unlock(&pool_lock);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161

/* Deterministic Fixed-Size Memory Pool Implementation */
 
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
 
/* Pool block header - embedded in each free block */
typedef struct pool_block {
    struct pool_block *next;
} pool_block_t;
 
/* Memory pool structure */
typedef struct {
    pool_block_t *free_list;        /* Head of free block list */
    uint8_t *pool_start;            /* Start of pool memory */
    uint8_t *pool_end;              /* End of pool memory */
    size_t block_size;              /* Size of each block */
    size_t total_blocks;            /* Total blocks in pool */
    volatile size_t free_blocks;    /* Currently free blocks */
    spinlock_t lock;                /* Thread safety */
#ifdef POOL_STATS
    size_t alloc_count;             /* Total allocations */
    size_t free_count;              /* Total frees */
    size_t high_water_mark;         /* Maximum blocks in use */
#endif
} memory_pool_t;
 
/* Initialize pool from static memory region */
void pool_init(memory_pool_t *pool, void *memory, 
               size_t memory_size, size_t block_size) {
    /* Ensure block size can hold the free list pointer */
    if (block_size < sizeof(pool_block_t)) {
        block_size = sizeof(pool_block_t);
    }
    
    /* Align block size */
    block_size = (block_size + sizeof(void*) - 1) & ~(sizeof(void*) - 1);
    
    pool->block_size = block_size;
    pool->pool_start = memory;
    pool->pool_end = (uint8_t*)memory + memory_size;
    pool->total_blocks = memory_size / block_size;
    pool->free_blocks = pool->total_blocks;
    pool->free_list = NULL;
    spinlock_init(&pool->lock);
    
    /* Link all blocks into free list */
    uint8_t *block = pool->pool_start;
    for (size_t i = 0; i < pool->total_blocks; i++) {
        pool_block_t *node = (pool_block_t *)block;
        node->next = pool->free_list;
        pool->free_list = node;
        block += block_size;
    }
    
#ifdef POOL_STATS
    pool->alloc_count = 0;
    pool->free_count = 0;
    pool->high_water_mark = 0;
#endif
}
 
/* Allocate block - O(1) GUARANTEED */
void *pool_alloc(memory_pool_t *pool) {
    spin_lock(&pool->lock);
    
    pool_block_t *block = pool->free_list;
    
    if (block != NULL) {
        /* Remove from free list - single pointer update */
        pool->free_list = block->next;
        pool->free_blocks--;
        
#ifdef POOL_STATS
        pool->alloc_count++;
        size_t in_use = pool->total_blocks - pool->free_blocks;
        if (in_use > pool->high_water_mark) {
            pool->high_water_mark = in_use;
        }
#endif
    }
    
    spin_unlock(&pool->lock);
    
    return block;  /* NULL if pool exhausted */
}
 
/* Free block - O(1) GUARANTEED */
void pool_free(memory_pool_t *pool, void *ptr) {
    if (ptr == NULL) return;
    
    /* Validate pointer is within pool */
    uint8_t *block = (uint8_t *)ptr;
    if (block < pool->pool_start || block >= pool->pool_end) {
        /* Invalid pointer - panic or log error */
        return;
    }
    
    /* Validate alignment */
    ptrdiff_t offset = block - pool->pool_start;
    if (offset % pool->block_size != 0) {
        /* Misaligned pointer */
        return;
    }
    
    spin_lock(&pool->lock);
    
    /* Add to front of free list - single pointer update */
    pool_block_t *node = (pool_block_t *)ptr;
    node->next = pool->free_list;
    pool->free_list = node;
    pool->free_blocks++;
    
#ifdef POOL_STATS
    pool->free_count++;
#endif
    
    spin_unlock(&pool->lock);
}
 
/* Check if pool can satisfy allocation - O(1) */
bool pool_can_alloc(memory_pool_t *pool) {
    return pool->free_blocks > 0;
}
 
/* ============================================
 * Lock-Free Pool for ISR-Safe Allocation
 * ============================================ */
 
typedef struct {
    pool_block_t * volatile free_list;
    uint8_t *pool_start;
    size_t block_size;
    size_t total_blocks;
} lockfree_pool_t;
 
/* ISR-safe allocation using compare-and-swap */
void *lockfree_pool_alloc(lockfree_pool_t *pool) {
    pool_block_t *head;
    pool_block_t *next;
    
    do {
        head = pool->free_list;
        if (head == NULL) {
            return NULL;  /* Pool exhausted */
        }
        next = head->next;
    } while (!__sync_bool_compare_and_swap(&pool->free_list, head, next));
    
    return head;
}
 
void lockfree_pool_free(lockfree_pool_t *pool, void *ptr) {
    pool_block_t *block = (pool_block_t *)ptr;
    pool_block_t *head;
    
    do {
        head = pool->free_list;
        block->next = head;
    } while (!__sync_bool_compare_and_swap(&pool->free_list, head, block));
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136

/* Memory Locking for Real-Time Applications */
 
#include <sys/mman.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
 
/* ============================================
 * System-Wide Memory Locking
 * ============================================ */
 
void lock_all_memory(void) {
    /* MCL_CURRENT: Lock all currently mapped pages */
    /* MCL_FUTURE: Lock all pages mapped in the future */
    if (mlockall(MCL_CURRENT | MCL_FUTURE) != 0) {
        perror("mlockall failed");
        fprintf(stderr, "Try running as root or increase RLIMIT_MEMLOCK\n");
        exit(1);
    }
    
    printf("All memory locked successfully\n");
}
 
/* ============================================
 * Pre-faulting Stack Memory
 * ============================================ */
 
#define STACK_SIZE (1024 * 1024)  /* 1MB stack */
 
void prefault_stack(void) {
    /* Allocate array on stack and touch all pages */
    volatile char stack_buffer[STACK_SIZE];
    
    /* Touch each page to ensure it's faulted in */
    long page_size = sysconf(_SC_PAGESIZE);
    
    for (size_t i = 0; i < STACK_SIZE; i += page_size) {
        stack_buffer[i] = 0;
    }
    
    /* After this function returns, stack pages are resident */
}
 
/* ============================================
 * Pre-faulting Heap Memory
 * ============================================ */
 
void prefault_heap(void *buffer, size_t size) {
    long page_size = sysconf(_SC_PAGESIZE);
    volatile char *ptr = (volatile char *)buffer;
    
    /* Touch each page */
    for (size_t i = 0; i < size; i += page_size) {
        ptr[i] = 0;  /* Write triggers copy-on-write if needed */
    }
}
 
/* ============================================
 * Real-Time Memory Preparation
 * ============================================ */
 
typedef struct {
    void *buffer;
    size_t size;
} rt_buffer_t;
 
#define MAX_RT_BUFFERS 16
static rt_buffer_t rt_buffers[MAX_RT_BUFFERS];
static int rt_buffer_count = 0;
 
void prepare_realtime_buffer(size_t size) {
    if (rt_buffer_count >= MAX_RT_BUFFERS) {
        fprintf(stderr, "Too many RT buffers\n");
        exit(1);
    }
    
    /* Allocate aligned memory */
    void *buffer;
    if (posix_memalign(&buffer, sysconf(_SC_PAGESIZE), size) != 0) {
        perror("posix_memalign failed");
        exit(1);
    }
    
    /* Lock the memory */
    if (mlock(buffer, size) != 0) {
        perror("mlock failed");
        free(buffer);
        exit(1);
    }
    
    /* Pre-fault all pages */
    prefault_heap(buffer, size);
    
    /* Register for cleanup */
    rt_buffers[rt_buffer_count].buffer = buffer;
    rt_buffers[rt_buffer_count].size = size;
    rt_buffer_count++;
    
    printf("Allocated and locked %zu bytes at %p\n", size, buffer);
}
 
/* ============================================
 * Complete Real-Time Memory Setup
 * ============================================ */
 
void setup_realtime_memory(void) {
    /* 1. Check and set resource limits */
    struct rlimit rlim;
    getrlimit(RLIMIT_MEMLOCK, &rlim);
    printf("Current MEMLOCK limit: %lu (soft), %lu (hard)\n",
           rlim.rlim_cur, rlim.rlim_max);
    
    if (rlim.rlim_cur < 1024*1024*100) {  /* 100MB */
        rlim.rlim_cur = rlim.rlim_max = RLIM_INFINITY;
        if (setrlimit(RLIMIT_MEMLOCK, &rlim) != 0) {
            fprintf(stderr, "Warning: Cannot increase MEMLOCK limit\n");
        }
    }
    
    /* 2. Lock all current and future memory */
    lock_all_memory();
    
    /* 3. Pre-fault stack */
    prefault_stack();
    
    /* 4. Pre-allocate and lock application buffers */
    prepare_realtime_buffer(1024 * 1024);  /* 1MB working buffer */
    prepare_realtime_buffer(64 * 1024);    /* 64KB message buffer */
    
    /* 5. Disable core dumps (they cause page-out) */
    struct rlimit core_rlim = {0, 0};
    setrlimit(RLIMIT_CORE, &core_rlim);
    
    printf("Real-time memory setup complete\n");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102

/* TLSF (Two-Level Segregated Fit) Allocator Overview
 * 
 * TLSF is a real-time allocator providing O(1) malloc and free
 * with bounded fragmentation. Used in many RTOS.
 */
 
#include <stdint.h>
 
/* First level: powers of 2 (16, 32, 64, 128, ...) */
#define FL_INDEX_COUNT  16
/* Second level: subdivisions within each power of 2 */
#define SL_INDEX_COUNT  16
 
typedef struct {
    /* Bitmaps for quick free block lookup */
    uint32_t fl_bitmap;                     /* First-level */
    uint32_t sl_bitmap[FL_INDEX_COUNT];     /* Second-level */
    
    /* Segregated free lists */
    block_header_t *blocks[FL_INDEX_COUNT][SL_INDEX_COUNT];
    
    /* Memory pool */
    void *pool_start;
    size_t pool_size;
} tlsf_t;
 
/* Calculate TLSF indices from size - O(1) using CLZ */
static inline void mapping_insert(size_t size, 
                                  int *fl, int *sl) {
    if (size < 256) {
        *fl = 0;
        *sl = (size >> 4) & 0xF;  /* Direct mapping for small sizes */
    } else {
        /* Use count-leading-zeros for O(1) calculation */
        int t = 31 - __builtin_clz(size);
        *fl = t - 4;
        *sl = (size >> (t - 4)) & 0xF;
    }
}
 
/* Find suitable free block - O(1) using bitmaps */
static block_header_t *find_free_block(tlsf_t *tlsf, 
                                        int *fl, int *sl) {
    /* Find first first-level list with blocks >= our size class */
    uint32_t fl_map = tlsf->fl_bitmap & (~0U << *fl);
    
    if (fl_map == 0) {
        return NULL;  /* No suitable block - O(1) failure detection */
    }
    
    *fl = __builtin_ctz(fl_map);  /* First set bit */
    
    /* Find first second-level list */
    uint32_t sl_map = tlsf->sl_bitmap[*fl];
    *sl = __builtin_ctz(sl_map);
    
    /* Return head of free list */
    return tlsf->blocks[*fl][*sl];  /* O(1) */
}
 
/* Allocate memory - O(1) GUARANTEED */
void *tlsf_malloc(tlsf_t *tlsf, size_t size) {
    /* 1. Calculate size class - O(1) */
    size_t adjusted_size = adjust_size(size);
    int fl, sl;
    mapping_insert(adjusted_size, &fl, &sl);
    
    /* 2. Find free block - O(1) using bitmaps */
    block_header_t *block = find_free_block(tlsf, &fl, &sl);
    
    if (block == NULL) {
        return NULL;  /* No memory - deterministic failure */
    }
    
    /* 3. Remove from free list - O(1) */
    remove_from_free_list(tlsf, block, fl, sl);
    
    /* 4. Split if too large - O(1) */
    if (should_split(block, adjusted_size)) {
        block_header_t *remaining = split_block(block, adjusted_size);
        insert_free_block(tlsf, remaining);
    }
    
    /* 5. Mark as used, return - O(1) */
    block->header |= BLOCK_USED;
    return get_payload_ptr(block);
}
 
/* Free memory - O(1) GUARANTEED */
void tlsf_free(tlsf_t *tlsf, void *ptr) {
    block_header_t *block = get_block_from_payload(ptr);
    
    /* Mark as free */
    block->header &= ~BLOCK_USED;
    
    /* Coalesce with neighbors - O(1) due to boundary tags */
    block = coalesce_prev(tlsf, block);
    block = coalesce_next(tlsf, block);
    
    /* Insert into appropriate free list - O(1) */
    insert_free_block(tlsf, block);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

/* Safety-Critical Memory Patterns */
 
/* ============================================
 * Stack Usage Analysis Support
 * ============================================ */
 
/* Stack filling pattern for high-water-mark detection */
#define STACK_FILL_PATTERN 0xDEADBEEF
 
void fill_stack_with_pattern(uint32_t *stack_base, size_t size_words) {
    for (size_t i = 0; i < size_words; i++) {
        stack_base[i] = STACK_FILL_PATTERN;
    }
}
 
size_t measure_stack_usage(uint32_t *stack_base, size_t size_words) {
    size_t unused = 0;
    
    /* Count words still containing pattern (unused stack) */
    while (unused < size_words && 
           stack_base[unused] == STACK_FILL_PATTERN) {
        unused++;
    }
    
    return (size_words - unused) * sizeof(uint32_t);
}
 
/* ============================================
 * Memory Corruption Detection
 * ============================================ */
 
/* Guard words around critical data structures */
#define GUARD_WORD_HEAD 0xFEEDFACE
#define GUARD_WORD_TAIL 0xCAFEBABE
 
typedef struct {
    uint32_t guard_head;
    flight_control_data_t data;
    uint32_t guard_tail;
} guarded_flight_data_t;
 
bool validate_guards(guarded_flight_data_t *gd) {
    if (gd->guard_head != GUARD_WORD_HEAD) {
        report_memory_corruption(gd, CORRUPTION_HEAD);
        return false;
    }
    
    if (gd->guard_tail != GUARD_WORD_TAIL) {
        report_memory_corruption(gd, CORRUPTION_TAIL);
        return false;
    }
    
    return true;
}
 
/* ============================================
 * Defensive Pointer Handling
 * ============================================ */
 
/* Safe pointer dereference with range check */
#define SAFE_PTR_READ(ptr, region_start, region_size, result) \
    do { \
        if ((uintptr_t)(ptr) >= (uintptr_t)(region_start) && \
            (uintptr_t)(ptr) + sizeof(*(ptr)) <= \
            (uintptr_t)(region_start) + (region_size)) { \
            (result) = *(ptr); \
        } else { \
            report_pointer_error(ptr, __FILE__, __LINE__); \
            (result) = get_safe_default_value(); \
        } \
    } while(0)
 
/* Null-check macro with error reporting */
#define CHECK_NULL(ptr, action_on_null) \
    do { \
        if ((ptr) == NULL) { \
            log_null_pointer_access(__FILE__, __LINE__, #ptr); \
            action_on_null; \
        } \
    } while(0)