diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/core/ao_list.h | 213 | ||||
| -rw-r--r-- | src/core/ao_task.c | 340 | ||||
| -rw-r--r-- | src/core/ao_task.h | 21 | ||||
| -rw-r--r-- | src/megametrum-v0.1/ao_megametrum.c | 1 | ||||
| -rw-r--r-- | src/megametrum-v0.1/ao_pins.h | 2 | ||||
| -rw-r--r-- | src/stm/ao_timer.c | 4 |
6 files changed, 564 insertions, 17 deletions
diff --git a/src/core/ao_list.h b/src/core/ao_list.h new file mode 100644 index 00000000..23cf1841 --- /dev/null +++ b/src/core/ao_list.h @@ -0,0 +1,213 @@ +/* + * Copyright © 2012 Keith Packard <keithp@keithp.com> + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; version 2 of the License. + * + * This program is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. + */ + +#ifndef _AO_LIST_H_ +#define _AO_LIST_H_ + +#include <stddef.h> + +struct ao_list { + struct ao_list *next, *prev; +}; + +static inline void +ao_list_init(struct ao_list *list) +{ + list->next = list->prev = list; +} + +static inline void +__ao_list_add(struct ao_list *list, struct ao_list *prev, struct ao_list *next) +{ + next->prev = list; + list->next = next; + list->prev = prev; + prev->next = list; +} + +/** + * Insert a new element after the given list head. The new element does not + * need to be initialised as empty list. + * The list changes from: + * head → some element → ... + * to + * head → new element → older element → ... + * + * Example: + * struct foo *newfoo = malloc(...); + * ao_list_add(&newfoo->entry, &bar->list_of_foos); + * + * @param entry The new element to prepend to the list. + * @param head The existing list. + */ +static inline void +ao_list_insert(struct ao_list *entry, struct ao_list *head) +{ + __ao_list_add(entry, head, head->next); +} + +/** + * Append a new element to the end of the list given with this list head. + * + * The list changes from: + * head → some element → ... → lastelement + * to + * head → some element → ... → lastelement → new element + * + * Example: + * struct foo *newfoo = malloc(...); + * ao_list_append(&newfoo->entry, &bar->list_of_foos); + * + * @param entry The new element to prepend to the list. + * @param head The existing list. + */ +static inline void +ao_list_append(struct ao_list *entry, struct ao_list *head) +{ + __ao_list_add(entry, head->prev, head); +} + +static inline void +__ao_list_del(struct ao_list *prev, struct ao_list *next) +{ + next->prev = prev; + prev->next = next; +} + +/** + * Remove the element from the list it is in. Using this function will reset + * the pointers to/from this element so it is removed from the list. It does + * NOT free the element itself or manipulate it otherwise. + * + * Using ao_list_del on a pure list head (like in the example at the top of + * this file) will NOT remove the first element from + * the list but rather reset the list as empty list. + * + * Example: + * ao_list_del(&foo->entry); + * + * @param entry The element to remove. + */ +static inline void +ao_list_del(struct ao_list *entry) +{ + __ao_list_del(entry->prev, entry->next); + ao_list_init(entry); +} + +/** + * Check if the list is empty. + * + * Example: + * ao_list_is_empty(&bar->list_of_foos); + * + * @return True if the list contains one or more elements or False otherwise. + */ +static inline uint8_t +ao_list_is_empty(struct ao_list *head) +{ + return head->next == head; +} + +/** + * Returns a pointer to the container of this list element. + * + * Example: + * struct foo* f; + * f = container_of(&foo->entry, struct foo, entry); + * assert(f == foo); + * + * @param ptr Pointer to the struct ao_list. + * @param type Data type of the list element. + * @param member Member name of the struct ao_list field in the list element. + * @return A pointer to the data struct containing the list head. + */ +#define ao_container_of(ptr, type, member) \ + (type *)((char *)(ptr) - offsetof(type, member)) + +/** + * Alias of ao_container_of + */ +#define ao_list_entry(ptr, type, member) \ + ao_container_of(ptr, type, member) + +/** + * Retrieve the first list entry for the given list pointer. + * + * Example: + * struct foo *first; + * first = ao_list_first_entry(&bar->list_of_foos, struct foo, list_of_foos); + * + * @param ptr The list head + * @param type Data type of the list element to retrieve + * @param member Member name of the struct ao_list field in the list element. + * @return A pointer to the first list element. + */ +#define ao_list_first_entry(ptr, type, member) \ + ao_list_entry((ptr)->next, type, member) + +/** + * Retrieve the last list entry for the given listpointer. + * + * Example: + * struct foo *first; + * first = ao_list_last_entry(&bar->list_of_foos, struct foo, list_of_foos); + * + * @param ptr The list head + * @param type Data type of the list element to retrieve + * @param member Member name of the struct ao_list field in the list element. + * @return A pointer to the last list element. + */ +#define ao_list_last_entry(ptr, type, member) \ + ao_list_entry((ptr)->prev, type, member) + +/** + * Loop through the list given by head and set pos to struct in the list. + * + * Example: + * struct foo *iterator; + * ao_list_for_each_entry(iterator, &bar->list_of_foos, entry) { + * [modify iterator] + * } + * + * This macro is not safe for node deletion. Use ao_list_for_each_entry_safe + * instead. + * + * @param pos Iterator variable of the type of the list elements. + * @param head List head + * @param member Member name of the struct ao_list in the list elements. + * + */ +#define ao_list_for_each_entry(pos, head, type, member) \ + for (pos = ao_container_of((head)->next, type, member); \ + &pos->member != (head); \ + pos = ao_container_of(pos->member.next, type, member)) + +/** + * Loop through the list, keeping a backup pointer to the element. This + * macro allows for the deletion of a list element while looping through the + * list. + * + * See ao_list_for_each_entry for more details. + */ +#define ao_list_for_each_entry_safe(pos, tmp, head, type, member) \ + for ((pos = ao_container_of((head)->next, type, member)), \ + (tmp = ao_container_of(pos->member.next, type, member)); \ + &pos->member != (head); \ + (pos = tmp), (tmp = ao_container_of(pos->member.next, type, member))) + +#endif /* _AO_LIST_H_ */ diff --git a/src/core/ao_task.c b/src/core/ao_task.c index df70b906..a11979f0 100644 --- a/src/core/ao_task.c +++ b/src/core/ao_task.c @@ -24,13 +24,18 @@ #include <ao_mpu.h> #endif +#define DEBUG 0 + #define AO_NO_TASK_INDEX 0xff __xdata struct ao_task * __xdata ao_tasks[AO_NUM_TASKS]; __data uint8_t ao_num_tasks; -__data uint8_t ao_cur_task_index; __xdata struct ao_task *__data ao_cur_task; +#if !HAS_TASK_QUEUE +static __data uint8_t ao_cur_task_index; +#endif + #ifdef ao_arch_task_globals ao_arch_task_globals #endif @@ -49,6 +54,225 @@ static inline void ao_check_stack(void) { #define ao_check_stack() #endif +#if HAS_TASK_QUEUE + +#define SLEEP_HASH_SIZE 17 + +static struct ao_list run_queue; +static struct ao_list alarm_queue; +static struct ao_list sleep_queue[SLEEP_HASH_SIZE]; + +static void +ao_task_to_run_queue(struct ao_task *task) +{ + ao_list_del(&task->queue); + ao_list_append(&task->queue, &run_queue); +} + +static struct ao_list * +ao_task_sleep_queue(void *wchan) +{ + return &sleep_queue[(uintptr_t) wchan % SLEEP_HASH_SIZE]; +} + +static void +ao_task_to_sleep_queue(struct ao_task *task, void *wchan) +{ + ao_list_del(&task->queue); + ao_list_append(&task->queue, ao_task_sleep_queue(wchan)); +} + +#if DEBUG +static void +ao_task_validate_alarm_queue(void) +{ + struct ao_task *alarm, *prev = NULL; + int i; + + if (ao_list_is_empty(&alarm_queue)) + return; + ao_list_for_each_entry(alarm, &alarm_queue, struct ao_task, alarm_queue) { + if (prev) { + if ((int16_t) (alarm->alarm - prev->alarm) < 0) { + ao_panic(1); + } + } + prev = alarm; + } + for (i = 0; i < ao_num_tasks; i++) { + alarm = ao_tasks[i]; + if (alarm->alarm) { + if (ao_list_is_empty(&alarm->alarm_queue)) + ao_panic(2); + } else { + if (!ao_list_is_empty(&alarm->alarm_queue)) + ao_panic(3); + } + } +} +#else +#define ao_task_validate_alarm_queue() +#endif + +static void +ao_task_to_alarm_queue(struct ao_task *task) +{ + struct ao_task *alarm; + ao_list_for_each_entry(alarm, &alarm_queue, struct ao_task, alarm_queue) { + if ((int16_t) (alarm->alarm - task->alarm) >= 0) { + ao_list_insert(&task->alarm_queue, alarm->alarm_queue.prev); + ao_task_validate_alarm_queue(); + return; + } + } + ao_list_append(&task->alarm_queue, &alarm_queue); + ao_task_validate_alarm_queue(); +} + +static void +ao_task_from_alarm_queue(struct ao_task *task) +{ + ao_list_del(&task->alarm_queue); + ao_task_validate_alarm_queue(); +} + +static void +ao_task_init_queue(struct ao_task *task) +{ + ao_list_init(&task->queue); + ao_list_init(&task->alarm_queue); +} + +static void +ao_task_exit_queue(struct ao_task *task) +{ + ao_list_del(&task->queue); + ao_list_del(&task->alarm_queue); +} + +void +ao_task_check_alarm(uint16_t tick) +{ + struct ao_task *alarm, *next; + int i; + + if (ao_num_tasks == 0) + return; + ao_list_for_each_entry_safe(alarm, next, &alarm_queue, struct ao_task, alarm_queue) { + if ((int16_t) (tick - alarm->alarm) < 0) + break; + alarm->alarm = 0; + ao_task_from_alarm_queue(alarm); + ao_task_to_run_queue(alarm); + } +} + +void +ao_task_init(void) +{ + uint8_t i; + ao_list_init(&run_queue); + ao_list_init(&alarm_queue); + for (i = 0; i < SLEEP_HASH_SIZE; i++) + ao_list_init(&sleep_queue[i]); +} + +#if DEBUG +static uint8_t +ao_task_validate_queue(struct ao_task *task) +{ + uint32_t flags; + struct ao_task *m; + uint8_t ret = 0; + struct ao_list *queue; + + flags = ao_arch_irqsave(); + if (task->wchan) { + queue = ao_task_sleep_queue(task->wchan); + ret |= 2; + } else { + queue = &run_queue; + ret |= 4; + } + ao_list_for_each_entry(m, queue, struct ao_task, queue) { + if (m == task) { + ret |= 1; + break; + } + } + ao_arch_irqrestore(flags); + return ret; +} + +static uint8_t +ao_task_validate_alarm(struct ao_task *task) +{ + uint32_t flags; + struct ao_task *m; + uint8_t ret = 0; + + flags = ao_arch_irqsave(); + if (task->alarm == 0) + return 0xff; + ao_list_for_each_entry(m, &alarm_queue, struct ao_task, alarm_queue) { + if (m == task) + ret |= 1; + else { + if (!(ret&1)) { + if ((int16_t) (m->alarm - task->alarm) > 0) + ret |= 2; + } else { + if ((int16_t) (task->alarm - m->alarm) > 0) + ret |= 4; + } + } + } + ao_arch_irqrestore(flags); + return ret; +} + + +static void +ao_task_validate(void) +{ + uint8_t i; + struct ao_task *task; + uint8_t ret; + + for (i = 0; i < ao_num_tasks; i++) { + task = ao_tasks[i]; + ret = ao_task_validate_queue(task); + if (!(ret & 1)) { + if (ret & 2) + printf ("sleeping task not on sleep queue %s %08x\n", + task->name, task->wchan); + else + printf ("running task not on run queue %s\n", + task->name); + } + ret = ao_task_validate_alarm(task); + if (ret != 0xff) { + if (!(ret & 1)) + printf ("alarm task not on alarm queue %s %d\n", + task->name, task->alarm); + if (ret & 2) + printf ("alarm queue has sooner entries after %s %d\n", + task->name, task->alarm); + if (ret & 4) + printf ("alarm queue has later entries before %s %d\n", + task->name, task->alarm); + } + } +} +#else +#define ao_task_validate() +#endif + +#else +#define ao_task_to_run_queue(task) +#define ao_task_to_alarm_queue(task) +#endif + void ao_add_task(__xdata struct ao_task * task, void (*start)(void), __code char *name) __reentrant { @@ -63,7 +287,6 @@ ao_add_task(__xdata struct ao_task * task, void (*start)(void), __code char *nam if (t == ao_num_tasks) break; } - ao_tasks[ao_num_tasks++] = task; task->task_id = task_id; task->name = name; task->wchan = NULL; @@ -72,18 +295,29 @@ ao_add_task(__xdata struct ao_task * task, void (*start)(void), __code char *nam * to the start of the task */ ao_arch_init_stack(task, start); + ao_arch_critical( +#if HAS_TASK_QUEUE + ao_task_init_queue(task); + ao_task_to_run_queue(task); +#endif + ao_tasks[ao_num_tasks] = task; + ao_num_tasks++; + ); } -__xdata uint8_t ao_idle; - /* Task switching function. This must not use any stack variables */ void ao_yield(void) ao_arch_naked_define { ao_arch_save_regs(); +#if HAS_TASK_QUEUE + if (ao_cur_task == NULL) + ao_cur_task = ao_tasks[ao_num_tasks-1]; +#else if (ao_cur_task_index == AO_NO_TASK_INDEX) ao_cur_task_index = ao_num_tasks-1; +#endif else { #if HAS_SAMPLE_PROFILE @@ -104,6 +338,24 @@ ao_yield(void) ao_arch_naked_define /* Find a task to run. If there isn't any runnable task, * this loop will run forever, which is just fine */ +#if HAS_TASK_QUEUE + if (ao_cur_task->wchan == NULL) { + uint32_t flags; + flags = ao_arch_irqsave(); + ao_task_to_run_queue(ao_cur_task); + ao_arch_irqrestore(flags); + } + ao_cur_task = NULL; + + for (;;) { + ao_arch_memory_barrier(); + if (!ao_list_is_empty(&run_queue)) + break; + ao_arch_cpu_idle(); + } + + ao_cur_task = ao_list_first_entry(&run_queue, struct ao_task, queue); +#else { __pdata uint8_t ao_last_task_index = ao_cur_task_index; for (;;) { @@ -127,14 +379,15 @@ ao_yield(void) ao_arch_naked_define ao_arch_cpu_idle(); } #if HAS_SAMPLE_PROFILE - ao_cur_task->start = ao_sample_profile_timer_value(); + ao_cur_task->start = ao_sample_profile_timer_value(); #endif } +#endif #if HAS_STACK_GUARD ao_mpu_stack_guard(ao_cur_task->stack); #endif #if AO_CHECK_STACK - cli(); + ao_arch_block_interrupts(); in_yield = 0; #endif ao_arch_restore_stack(); @@ -143,7 +396,15 @@ ao_yield(void) ao_arch_naked_define uint8_t ao_sleep(__xdata void *wchan) { +#if HAS_TASK_QUEUE + uint32_t flags; + flags = ao_arch_irqsave(); +#endif ao_cur_task->wchan = wchan; +#if HAS_TASK_QUEUE + ao_task_to_sleep_queue(ao_cur_task, wchan); + ao_arch_irqrestore(flags); +#endif ao_yield(); if (ao_cur_task->wchan) { ao_cur_task->wchan = NULL; @@ -156,28 +417,62 @@ ao_sleep(__xdata void *wchan) void ao_wakeup(__xdata void *wchan) { - uint8_t i; +#if HAS_TASK_QUEUE + struct ao_task *sleep, *next; + struct ao_list *sleep_queue; + uint32_t flags; - ao_check_stack(); + if (ao_num_tasks == 0) + return; + sleep_queue = ao_task_sleep_queue(wchan); + flags = ao_arch_irqsave(); + ao_list_for_each_entry_safe(sleep, next, sleep_queue, struct ao_task, queue) { + if (sleep->wchan == wchan) { + sleep->wchan = NULL; + ao_task_to_run_queue(sleep); + } + } + ao_arch_irqrestore(flags); +#else + uint8_t i; for (i = 0; i < ao_num_tasks; i++) if (ao_tasks[i]->wchan == wchan) ao_tasks[i]->wchan = NULL; +#endif + ao_check_stack(); } void ao_alarm(uint16_t delay) { +#if HAS_TASK_QUEUE + uint32_t flags; /* Make sure we sleep *at least* delay ticks, which means adding * one to account for the fact that we may be close to the next tick */ + flags = ao_arch_irqsave(); +#endif if (!(ao_cur_task->alarm = ao_time() + delay + 1)) ao_cur_task->alarm = 1; +#if HAS_TASK_QUEUE + ao_task_to_alarm_queue(ao_cur_task); + ao_arch_irqrestore(flags); +#endif } void ao_clear_alarm(void) { +#if HAS_TASK_QUEUE + uint32_t flags; + + flags = ao_arch_irqsave(); +#endif ao_cur_task->alarm = 0; +#if HAS_TASK_QUEUE + ao_task_from_alarm_queue(ao_cur_task); + ao_arch_irqrestore(flags); +#endif } static __xdata uint8_t ao_forever; @@ -193,14 +488,22 @@ ao_delay(uint16_t ticks) void ao_exit(void) { - ao_arch_critical( - uint8_t i; - ao_num_tasks--; - for (i = ao_cur_task_index; i < ao_num_tasks; i++) - ao_tasks[i] = ao_tasks[i+1]; - ao_cur_task_index = AO_NO_TASK_INDEX; - ao_yield(); - ); + uint8_t i; + ao_arch_block_interrupts(); + ao_num_tasks--; +#if HAS_TASK_QUEUE + for (i = 0; i < ao_num_tasks; i++) + if (ao_tasks[i] == ao_cur_task) + break; + ao_task_exit_queue(ao_cur_task); +#else + i = ao_cur_task_index; + ao_cur_task_index = AO_NO_TASK_INDEX; +#endif + for (; i < ao_num_tasks; i++) + ao_tasks[i] = ao_tasks[i+1]; + ao_cur_task = NULL; + ao_yield(); /* we'll never get back here */ } @@ -216,12 +519,17 @@ ao_task_info(void) task->name, (int) task->wchan); } +#if HAS_TASK_QUEUE + ao_task_validate(); +#endif } void ao_start_scheduler(void) { +#if !HAS_TASK_QUEUE ao_cur_task_index = AO_NO_TASK_INDEX; +#endif ao_cur_task = NULL; ao_yield(); } diff --git a/src/core/ao_task.h b/src/core/ao_task.h index 4319d632..b3f152a0 100644 --- a/src/core/ao_task.h +++ b/src/core/ao_task.h @@ -17,6 +17,9 @@ #ifndef _AO_TASK_H_ #define _AO_TASK_H_ +#if HAS_TASK_QUEUE +#include <ao_list.h> +#endif /* An AltOS task */ struct ao_task { @@ -25,6 +28,10 @@ struct ao_task { ao_arch_task_members /* any architecture-specific fields */ uint8_t task_id; /* unique id */ __code char *name; /* task name */ +#if HAS_TASK_QUEUE + struct ao_list queue; + struct ao_list alarm_queue; +#endif uint8_t stack[AO_STACK_SIZE]; /* saved stack */ #if HAS_SAMPLE_PROFILE uint32_t ticks; @@ -39,7 +46,6 @@ struct ao_task { extern __xdata struct ao_task * __xdata ao_tasks[AO_NUM_TASKS]; extern __data uint8_t ao_num_tasks; -extern __data uint8_t ao_cur_task_index; extern __xdata struct ao_task *__data ao_cur_task; /* @@ -74,6 +80,12 @@ ao_yield(void) ao_arch_naked_declare; void ao_add_task(__xdata struct ao_task * task, void (*start)(void), __code char *name) __reentrant; +#if HAS_TASK_QUEUE +/* Called on timer interrupt to check alarms */ +void +ao_task_check_alarm(uint16_t tick); +#endif + /* Terminate the current task */ void ao_exit(void); @@ -86,4 +98,11 @@ ao_task_info(void); void ao_start_scheduler(void); +#if HAS_TASK_QUEUE +void +ao_task_init(void); +#else +#define ao_task_init() +#endif + #endif diff --git a/src/megametrum-v0.1/ao_megametrum.c b/src/megametrum-v0.1/ao_megametrum.c index 43c2292d..cb1eb417 100644 --- a/src/megametrum-v0.1/ao_megametrum.c +++ b/src/megametrum-v0.1/ao_megametrum.c @@ -41,6 +41,7 @@ main(void) ao_mpu_init(); #endif + ao_task_init(); ao_serial_init(); ao_led_init(LEDS_AVAILABLE); ao_led_on(AO_LED_GREEN); diff --git a/src/megametrum-v0.1/ao_pins.h b/src/megametrum-v0.1/ao_pins.h index e4c8c8fb..5ae80ac5 100644 --- a/src/megametrum-v0.1/ao_pins.h +++ b/src/megametrum-v0.1/ao_pins.h @@ -18,6 +18,8 @@ #ifndef _AO_PINS_H_ #define _AO_PINS_H_ +#define HAS_TASK_QUEUE 1 + /* 8MHz High speed external crystal */ #define AO_HSE 8000000 diff --git a/src/stm/ao_timer.c b/src/stm/ao_timer.c index d82a803e..d69035f8 100644 --- a/src/stm/ao_timer.c +++ b/src/stm/ao_timer.c @@ -16,6 +16,7 @@ */ #include "ao.h" +#include <ao_task.h> volatile __data AO_TICK_TYPE ao_tick_count; @@ -42,6 +43,9 @@ void stm_tim6_isr(void) if (stm_tim6.sr & (1 << STM_TIM67_SR_UIF)) { stm_tim6.sr = 0; ++ao_tick_count; +#if HAS_TASK_QUEUE + ao_task_check_alarm((uint16_t) ao_tick_count); +#endif #if AO_DATA_ALL if (++ao_data_count == ao_data_interval) { ao_data_count = 0; |