kern
view src/sched.c @ 73:b4b7198986a6
fixed a potential null dereference when deleting a bug in the redblack tree
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Sat, 15 Oct 2011 08:06:10 +0300 |
| parents | 437360696883 |
| children |
line source
1 #include <stdio.h>
2 #include <assert.h>
3 #include "sched.h"
4 #include "proc.h"
5 #include "intr.h"
6 #include "asmops.h"
7 #include "config.h"
9 #define EMPTY(q) ((q)->head == 0)
11 struct proc_list {
12 struct process *head, *tail;
13 };
15 static void idle_proc(void);
16 static void ins_back(struct proc_list *list, struct process *proc);
17 static void ins_front(struct proc_list *list, struct process *proc);
18 static void remove(struct proc_list *list, struct process *proc);
19 static int hash_addr(void *addr);
21 static struct proc_list runq;
22 static struct proc_list zombieq;
24 #define HTBL_SIZE 101
25 static struct proc_list wait_htable[HTBL_SIZE];
28 void schedule(void)
29 {
30 disable_intr();
32 if(EMPTY(&runq)) {
33 if(!get_current_proc()) {
34 /* we're already in the idle process, don't reenter it
35 * or you'll fill up the stack very quickly.
36 */
37 return;
38 }
40 idle_proc();
41 return;
42 }
44 /* if the current process exhausted its timeslice,
45 * move it to the back of the queue.
46 */
47 if(runq.head->ticks_left <= 0) {
48 if(runq.head->next) {
49 struct process *proc = runq.head;
50 remove(&runq, proc);
51 ins_back(&runq, proc);
52 }
54 /* start a new timeslice */
55 runq.head->ticks_left = TIMESLICE_TICKS;
56 }
58 /* always enter context_switch with interrupts disabled */
59 context_switch(runq.head->id);
60 }
62 void add_proc(int pid)
63 {
64 int istate;
65 struct process *proc;
67 istate = get_intr_state();
68 disable_intr();
70 proc = get_process(pid);
72 ins_back(&runq, proc);
73 proc->state = STATE_RUNNABLE;
75 set_intr_state(istate);
76 }
78 void remove_proc(int pid)
79 {
80 int istate;
81 struct process *proc;
83 istate = get_intr_state();
84 disable_intr();
86 proc = get_process(pid);
87 remove(&runq, proc);
89 set_intr_state(istate);
90 }
92 /* block the process until we get a wakeup call for address ev */
93 void wait(void *wait_addr)
94 {
95 struct process *p;
96 int hash_idx;
98 disable_intr();
100 p = get_current_proc();
101 assert(p);
103 /* remove it from the runqueue ... */
104 remove(&runq, p);
106 /* and place it in the wait hash table based on sleep_addr */
107 hash_idx = hash_addr(wait_addr);
108 ins_back(wait_htable + hash_idx, p);
110 p->state = STATE_BLOCKED;
111 p->wait_addr = wait_addr;
113 /* call the scheduler to give time to another process */
114 schedule();
115 }
117 /* wake up all the processes sleeping on this address */
118 void wakeup(void *wait_addr)
119 {
120 int hash_idx;
121 struct process *iter;
122 struct proc_list *list;
124 hash_idx = hash_addr(wait_addr);
125 list = wait_htable + hash_idx;
127 iter = list->head;
128 while(iter) {
129 if(iter->wait_addr == wait_addr) {
130 /* found one, remove it, and make it runnable */
131 struct process *p = iter;
132 iter = iter->next;
134 remove(list, p);
135 p->state = STATE_RUNNABLE;
136 ins_back(&runq, p);
137 } else {
138 iter = iter->next;
139 }
140 }
141 }
143 static void idle_proc(void)
144 {
145 /* make sure we send any pending EOIs if needed.
146 * end_of_irq will actually check if it's needed first.
147 */
148 struct intr_frame *ifrm = get_intr_frame();
149 end_of_irq(INTR_TO_IRQ(ifrm->inum));
151 set_current_pid(0);
153 printf("idle loop is running\n");
155 /* make sure interrupts are enabled before halting */
156 while(EMPTY(&runq)) {
157 enable_intr();
158 halt_cpu();
159 disable_intr();
160 }
161 }
164 /* list operations */
165 static void ins_back(struct proc_list *list, struct process *proc)
166 {
167 if(EMPTY(list)) {
168 list->head = proc;
169 } else {
170 list->tail->next = proc;
171 }
173 proc->next = 0;
174 proc->prev = list->tail;
175 list->tail = proc;
176 }
178 static void ins_front(struct proc_list *list, struct process *proc)
179 {
180 if(EMPTY(list)) {
181 list->tail = proc;
182 } else {
183 list->head->prev = proc;
184 }
186 proc->next = list->head;
187 proc->prev = 0;
188 list->head = proc;
189 }
191 static void remove(struct proc_list *list, struct process *proc)
192 {
193 if(proc->prev) {
194 proc->prev->next = proc->next;
195 }
196 if(proc->next) {
197 proc->next->prev = proc->prev;
198 }
199 if(list->head == proc) {
200 list->head = proc->next;
201 }
202 if(list->tail == proc) {
203 list->tail = proc->prev;
204 }
205 }
207 static int hash_addr(void *addr)
208 {
209 return (uint32_t)addr % HTBL_SIZE;
210 }