Post-and-poke style sync for the ksched
[akaros.git] / kern / src / atomic.c
1 #ifdef __SHARC__
2 #pragma nosharc
3 #endif
4
5 #include <arch/arch.h>
6
7 #include <bitmask.h>
8 #include <atomic.h>
9 #include <error.h>
10 #include <string.h>
11 #include <assert.h>
12 #include <hashtable.h>
13 #include <smp.h>
14
15 void increase_lock_depth(uint32_t coreid)
16 {
17         per_cpu_info[coreid].lock_depth++;
18 }
19
20 void decrease_lock_depth(uint32_t coreid)
21 {
22         per_cpu_info[coreid].lock_depth--;
23 }
24
25 /* Inits a hashlock. */
26 void hashlock_init(struct hashlock *hl, unsigned int nr_entries)
27 {
28         hl->nr_entries = nr_entries;
29         /* this is the right way to do it, though memset is faster.  If we ever
30          * find that this is taking a lot of time, we can change it. */
31         for (int i = 0; i < hl->nr_entries; i++) {
32                 spinlock_init(&hl->locks[i]);
33         }
34 }
35
36 /* Helper, gets the specific spinlock for a hl/key combo. */
37 static spinlock_t *get_spinlock(struct hashlock *hl, long key)
38 {
39         /* using the hashtable's generic hash function */
40         return &hl->locks[__generic_hash((void*)key) % hl->nr_entries];
41 }
42
43 void hash_lock(struct hashlock *hl, long key)
44 {
45         spin_lock(get_spinlock(hl, key));
46 }
47
48 void hash_unlock(struct hashlock *hl, long key)
49 {
50         spin_unlock(get_spinlock(hl, key));
51 }
52
53 void hash_lock_irqsave(struct hashlock *hl, long key)
54 {
55         spin_lock_irqsave(get_spinlock(hl, key));
56 }
57
58 void hash_unlock_irqsave(struct hashlock *hl, long key)
59 {
60         spin_unlock_irqsave(get_spinlock(hl, key));
61 }
62
63 /* This is the 'post (work) and poke' style of sync.  We make sure the poke
64  * tracker's function runs.  Once this returns, the func either has run or is
65  * currently running (in case someone else is running now).  We won't wait or
66  * spin or anything, and it is safe to call this recursively (deeper in the
67  * call-graph).
68  *
69  * It's up to the caller to somehow post its work.  We'll also pass arg to the
70  * func, ONLY IF the caller is the one to execute it - so there's no guarantee
71  * the func(specific_arg) combo will actually run.  It's more for info
72  * purposes/optimizations/etc.  If no one uses it, I'll get rid of it. */
73 void poke(struct poke_tracker *tracker, void *arg)
74 {
75         atomic_set(&tracker->need_to_run, TRUE);
76         /* will need to repeatedly do it if someone keeps posting work */
77         do {
78                 /* want an wrmb() btw posting work/need_to_run and in_progress.  the
79                  * swap provides the HW mb. just need a cmb, which we do in the loop to
80                  * cover the iterations (even though i can't imagine the compiler
81                  * reordering the check it needed to do for the branch).. */
82                 cmb();
83                 /* poke / make sure someone does it.  if we get a TRUE (1) back, someone
84                  * is already running and will deal with the posted work.  (probably on
85                  * their next loop).  if we got a 0 back, we won the race and have the
86                  * 'lock'. */
87                 if (atomic_swap(&tracker->run_in_progress, TRUE))
88                         return;
89                 /* if we're here, then we're the one who needs to run the func. */
90                 /* clear the 'need to run', since we're running it now.  new users will
91                  * set it again.  this write needs to be wmb()'d after in_progress.  the
92                  * swap provided the HW mb(). */
93                 cmb();
94                 atomic_set(&tracker->need_to_run, FALSE);       /* no internal HW mb */
95                 /* run the actual function.  the poke sync makes sure only one caller is
96                  * in that func at a time. */
97                 assert(tracker->func);
98                 tracker->func(arg);
99                 wmb();  /* ensure the in_prog write comes after the run_again. */
100                 atomic_set(&tracker->run_in_progress, FALSE);   /* no internal HW mb */
101                 /* in_prog write must come before run_again read */
102                 wrmb();
103         } while (atomic_read(&tracker->need_to_run));   /* while there's more work*/
104 }
105
106 // Must be called in a pair with waiton_checklist
107 int commit_checklist_wait(checklist_t* list, checklist_mask_t* mask)
108 {
109         assert(list->mask.size == mask->size);
110         // abort if the list is locked.  this will protect us from trying to commit
111         // and thus spin on a checklist that we are already waiting on.  it is
112         // still possible to not get the lock, but the holder is on another core.
113         // Or, bail out if we can see the list is already in use.  This check is
114         // just an optimization before we try to use the list for real.
115         if ((checklist_is_locked(list)) || !checklist_is_clear(list))
116                 return -EBUSY;
117
118         // possession of this lock means you can wait on it and set it
119         spin_lock_irqsave(&list->lock);
120         // wait til the list is available.  could have some adaptive thing here
121         // where it fails after X tries (like 500), gives up the lock, and returns
122         // an error code
123         while (!checklist_is_clear(list))
124                 cpu_relax();
125
126         // list is ours and clear, set it to the settings of our list
127         COPY_BITMASK(list->mask.bits, mask->bits, mask->size); 
128         return 0;
129 }
130
131 int commit_checklist_nowait(checklist_t* list, checklist_mask_t* mask)
132 {
133         int e = 0;
134         if ((e = commit_checklist_wait(list, mask)))
135                 return e;
136         // give up the lock, since we won't wait for completion
137         spin_unlock_irqsave(&list->lock);
138         return e;
139 }
140 // The deal with the lock:
141 // what if two different actors are waiting on the list, but for different reasons?
142 // part of the problem is we are doing both set and check via the same path
143 //
144 // aside: we made this a lot more difficult than the usual barriers or even 
145 // the RCU grace-period checkers, since we have to worry about this construct
146 // being used by others before we are done with it.
147 //
148 // how about this: if we want to wait on this later, we just don't release the
149 // lock.  if we release it, then we don't care who comes in and grabs and starts
150 // checking the list.  
151 //      - regardless, there are going to be issues with people looking for a free 
152 //      item.  even if they grab the lock, they may end up waiting a while and 
153 //      wantint to bail (like test for a while, give up, move on, etc).  
154 //      - still limited in that only the setter can check, and only one person
155 //      can spinwait / check for completion.  if someone else tries to wait (wanting
156 //      completion), they may miss it if someone else comes in and grabs the lock
157 //      to use it for a new checklist
158 //              - if we had the ability to sleep and get woken up, we could have a 
159 //              queue.  actually, we could do a queue anyway, but they all spin
160 //              and it's the bosses responsibility to *wake* them
161
162 // Must be called after commit_checklist
163 // Assumed we held the lock if we ever call this
164 int waiton_checklist(checklist_t* list)
165 {
166         extern atomic_t outstanding_calls;
167         // can consider breakout out early, like above, and erroring out
168         while (!checklist_is_clear(list))
169                 cpu_relax();
170         spin_unlock_irqsave(&list->lock);
171         // global counter of wrappers either waited on or being contended for.
172         atomic_dec(&outstanding_calls);
173         return 0;
174 }
175
176 // like waiton, but don't bother waiting either
177 int release_checklist(checklist_t* list)
178 {
179         spin_unlock_irqsave(&list->lock);
180         return 0;
181 }
182
183 // peaks in and sees if the list is locked with it's spinlock
184 int checklist_is_locked(checklist_t* list)
185 {
186         return spin_locked(&list->lock);
187 }
188
189 // no synch guarantees - just looks at the list
190 int checklist_is_clear(checklist_t* list)
191 {
192         return BITMASK_IS_CLEAR(list->mask.bits, list->mask.size);
193 }
194
195 // no synch guarantees - just resets the list to empty
196 void reset_checklist(checklist_t* list)
197 {
198         CLR_BITMASK(list->mask.bits, list->mask.size);
199 }
200
201 // CPU mask specific - this is how cores report in
202 void down_checklist(checklist_t* list)
203 {
204         CLR_BITMASK_BIT_ATOMIC(list->mask.bits, core_id());
205 }
206
207 /* Barriers */
208 void init_barrier(barrier_t* barrier, uint32_t count)
209 {
210         spinlock_init(&barrier->lock);
211         barrier->init_count = count;
212         barrier->current_count = count;
213         barrier->ready = 0;
214 }
215
216 void reset_barrier(barrier_t* barrier)
217 {
218         barrier->current_count = barrier->init_count;
219 }
220
221 // primitive barrier function.  all cores call this.
222 void waiton_barrier(barrier_t* barrier)
223 {
224         uint8_t local_ready = barrier->ready;
225
226         spin_lock_irqsave(&barrier->lock);
227         barrier->current_count--;
228         if (barrier->current_count) {
229                 spin_unlock_irqsave(&barrier->lock);
230                 while (barrier->ready == local_ready)
231                         cpu_relax();
232         } else {
233                 spin_unlock_irqsave(&barrier->lock);
234                 reset_barrier(barrier);
235                 wmb();
236                 barrier->ready++;
237         }
238 }