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