![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to gsync.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GnuMach] / Gnu-Mach / kern|
Return to gsync.c CVS log | Up to [GnuMach] / Gnu-Mach / kern |
1.1 root 1: /* Copyright (C) 2016 Free Software Foundation, Inc.
2: Contributed by Agustina Arzille <[email protected]>, 2016.
3:
4: This program is free software; you can redistribute it and/or
5: modify it under the terms of the GNU General Public License
6: as published by the Free Software Foundation; either
1.1.1.2 ! root 7: version 2 of the license, or (at your option) any later version.
1.1 root 8:
9: This program is distributed in the hope that it will be useful,
10: but WITHOUT ANY WARRANTY; without even the implied warranty of
11: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12: GNU General Public License for more details.
13:
14: You should have received a copy of the GNU General Public
15: License along with this program; if not, see
16: <http://www.gnu.org/licenses/>.
17: */
18:
19: #include <kern/gsync.h>
20: #include <kern/sched_prim.h>
21: #include <kern/thread.h>
22: #include <kern/lock.h>
23: #include <kern/list.h>
24: #include <vm/vm_map.h>
25:
26: /* An entry in the global hash table. */
27: struct gsync_hbucket
28: {
29: struct list entries;
30: decl_simple_lock_data (, lock)
31: };
32:
33: /* A key used to uniquely identify an address that a thread is
34: * waiting on. Its members' values depend on whether said
35: * address is shared or task-local. */
36: struct gsync_key
37: {
38: unsigned long u;
39: unsigned long v;
40: };
41:
42: /* A thread that is blocked on an address with 'gsync_wait'. */
43: struct gsync_waiter
44: {
45: struct list link;
46: struct gsync_key key;
47: thread_t waiter;
48: };
49:
50: #define GSYNC_NBUCKETS 512
51: static struct gsync_hbucket gsync_buckets[GSYNC_NBUCKETS];
52:
53: void gsync_setup (void)
54: {
55: int i;
56: for (i = 0; i < GSYNC_NBUCKETS; ++i)
57: {
58: list_init (&gsync_buckets[i].entries);
59: simple_lock_init (&gsync_buckets[i].lock);
60: }
61: }
62:
63: /* Convenience comparison functions for gsync_key's. */
64:
65: static inline int
66: gsync_key_eq (const struct gsync_key *lp,
67: const struct gsync_key *rp)
68: {
69: return (lp->u == rp->u && lp->v == rp->v);
70: }
71:
72: static inline int
73: gsync_key_lt (const struct gsync_key *lp,
74: const struct gsync_key *rp)
75: {
76: return (lp->u < rp->u || (lp->u == rp->u && lp->v < rp->v));
77: }
78:
79: #define MIX2_LL(x, y) ((((x) << 5) | ((x) >> 27)) ^ (y))
80:
81: static inline unsigned int
82: gsync_key_hash (const struct gsync_key *keyp)
83: {
84: unsigned int ret = sizeof (void *);
85: #ifndef __LP64__
86: ret = MIX2_LL (ret, keyp->u);
87: ret = MIX2_LL (ret, keyp->v);
88: #else
89: ret = MIX2_LL (ret, keyp->u & ~0U);
90: ret = MIX2_LL (ret, keyp->u >> 32);
91: ret = MIX2_LL (ret, keyp->v & ~0U);
92: ret = MIX2_LL (ret, keyp->v >> 32);
93: #endif
94: return (ret);
95: }
96:
97: /* Test if the passed VM Map can access the address ADDR. The
98: * parameter FLAGS is used to specify the width and protection
99: * of the address. */
100: static int
101: valid_access_p (vm_map_t map, vm_offset_t addr, int flags)
102: {
103: vm_prot_t prot = VM_PROT_READ |
104: ((flags & GSYNC_MUTATE) ? VM_PROT_WRITE : 0);
105: vm_offset_t size = sizeof (unsigned int) *
106: ((flags & GSYNC_QUAD) ? 2 : 1);
107:
108: vm_map_entry_t entry;
109: return (vm_map_lookup_entry (map, addr, &entry) &&
110: entry->vme_end >= addr + size &&
111: (prot & entry->protection) == prot);
112: }
113:
114: /* Given a task and an address, initialize the key at *KEYP and
115: * return the corresponding bucket in the global hash table. */
116: static int
117: gsync_fill_key (task_t task, vm_offset_t addr,
118: int flags, struct gsync_key *keyp)
119: {
120: if (flags & GSYNC_SHARED)
121: {
122: /* For a shared address, we need the VM object
123: * and offset as the keys. */
124: vm_map_t map = task->map;
125: vm_prot_t prot = VM_PROT_READ |
126: ((flags & GSYNC_MUTATE) ? VM_PROT_WRITE : 0);
127: vm_map_version_t ver;
128: vm_prot_t rpr;
129: vm_object_t obj;
130: vm_offset_t off;
131: boolean_t wired_p;
132:
133: if (unlikely (vm_map_lookup (&map, addr, prot, &ver,
134: &obj, &off, &rpr, &wired_p) != KERN_SUCCESS))
135: return (-1);
136:
137: /* The VM object is returned locked. However, we check the
138: * address' accessibility later, so we can release it. */
139: vm_object_unlock (obj);
140:
141: keyp->u = (unsigned long)obj;
142: keyp->v = (unsigned long)off;
143: }
144: else
145: {
146: /* Task-local address. The keys are the task's map and
147: * the virtual address itself. */
148: keyp->u = (unsigned long)task->map;
149: keyp->v = (unsigned long)addr;
150: }
151:
152: return ((int)(gsync_key_hash (keyp) % GSYNC_NBUCKETS));
153: }
154:
155: static inline struct gsync_waiter*
156: node_to_waiter (struct list *nodep)
157: {
158: return (list_entry (nodep, struct gsync_waiter, link));
159: }
160:
161: static inline struct list*
162: gsync_find_key (const struct list *entries,
163: const struct gsync_key *keyp, int *exactp)
164: {
165: /* Look for a key that matches. We take advantage of the fact
166: * that the entries are sorted to break out of the loop as
167: * early as possible. */
168: struct list *runp;
169: list_for_each (entries, runp)
170: {
171: struct gsync_waiter *p = node_to_waiter (runp);
172: if (gsync_key_lt (keyp, &p->key))
173: break;
174: else if (gsync_key_eq (keyp, &p->key))
175: {
176: if (exactp != 0)
177: *exactp = 1;
178: break;
179: }
180: }
181:
182: return (runp);
183: }
184:
185: kern_return_t gsync_wait (task_t task, vm_offset_t addr,
186: unsigned int lo, unsigned int hi, natural_t msec, int flags)
187: {
1.1.1.2 ! root 188: if (unlikely (task != current_task()))
! 189: /* Not implemented yet. */
! 190: return (KERN_FAILURE);
! 191:
1.1 root 192: struct gsync_waiter w;
193: int bucket = gsync_fill_key (task, addr, flags, &w.key);
194:
195: if (unlikely (bucket < 0))
196: return (KERN_INVALID_ADDRESS);
197:
1.1.1.2 ! root 198: /* Test that the address is actually valid for the
1.1 root 199: * given task. Do so with the read-lock held in order
200: * to prevent memory deallocations. */
201: vm_map_lock_read (task->map);
202:
1.1.1.2 ! root 203: struct gsync_hbucket *hbp = gsync_buckets + bucket;
! 204: simple_lock (&hbp->lock);
! 205:
1.1 root 206: if (unlikely (!valid_access_p (task->map, addr, flags)))
207: {
208: simple_unlock (&hbp->lock);
209: vm_map_unlock_read (task->map);
210: return (KERN_INVALID_ADDRESS);
211: }
212:
213: /* Before doing any work, check that the expected value(s)
214: * match the contents of the address. Otherwise, the waiting
215: * thread could potentially miss a wakeup. */
216: if (((unsigned int *)addr)[0] != lo ||
217: ((flags & GSYNC_QUAD) &&
218: ((unsigned int *)addr)[1] != hi))
219: {
220: simple_unlock (&hbp->lock);
221: vm_map_unlock_read (task->map);
222: return (KERN_INVALID_ARGUMENT);
223: }
224:
225: vm_map_unlock_read (task->map);
226:
227: /* Look for the first entry in the hash bucket that
228: * compares strictly greater than this waiter. */
229: struct list *runp;
230: list_for_each (&hbp->entries, runp)
231: {
232: struct gsync_waiter *p = node_to_waiter (runp);
233: if (gsync_key_lt (&w.key, &p->key))
234: break;
235: }
236:
237: /* Finally, add ourselves to the list and go to sleep. */
238: list_add (runp->prev, runp, &w.link);
239: w.waiter = current_thread ();
240:
241: if (flags & GSYNC_TIMED)
242: thread_will_wait_with_timeout (w.waiter, msec);
243: else
244: thread_will_wait (w.waiter);
245:
246: thread_sleep (0, (simple_lock_t)&hbp->lock, TRUE);
247:
248: /* We're back. */
249: kern_return_t ret = current_thread()->wait_result;
250: if (ret != THREAD_AWAKENED)
251: {
252: /* We were interrupted or timed out. */
253: simple_lock (&hbp->lock);
254: if (w.link.next != 0)
255: list_remove (&w.link);
256: simple_unlock (&hbp->lock);
257:
258: /* Map the error code. */
259: ret = ret == THREAD_INTERRUPTED ?
260: KERN_INTERRUPTED : KERN_TIMEDOUT;
261: }
262: else
263: ret = KERN_SUCCESS;
264:
265: return (ret);
266: }
267:
268: /* Remove a waiter from the queue, wake it up, and
269: * return the next node. */
270: static inline struct list*
271: dequeue_waiter (struct list *nodep)
272: {
273: struct list *nextp = list_next (nodep);
274: list_remove (nodep);
275: list_node_init (nodep);
276: clear_wait (node_to_waiter(nodep)->waiter,
277: THREAD_AWAKENED, FALSE);
278: return (nextp);
279: }
280:
281: kern_return_t gsync_wake (task_t task,
282: vm_offset_t addr, unsigned int val, int flags)
283: {
1.1.1.2 ! root 284: if (unlikely (task != current_task()))
! 285: /* Not implemented yet. */
! 286: return (KERN_FAILURE);
! 287:
1.1 root 288: struct gsync_key key;
289: int bucket = gsync_fill_key (task, addr, flags, &key);
290:
291: if (unlikely (bucket < 0))
292: return (KERN_INVALID_ADDRESS);
293:
294: kern_return_t ret = KERN_INVALID_ARGUMENT;
295:
1.1.1.2 ! root 296: vm_map_lock_read (task->map);
1.1 root 297: struct gsync_hbucket *hbp = gsync_buckets + bucket;
298: simple_lock (&hbp->lock);
299:
300: if (unlikely (!valid_access_p (task->map, addr, flags)))
301: {
302: simple_unlock (&hbp->lock);
303: vm_map_unlock_read (task->map);
304: return (KERN_INVALID_ADDRESS);
305: }
306:
307: if (flags & GSYNC_MUTATE)
308: /* Set the contents of the address to the specified value,
309: * even if we don't end up waking any threads. Note that
310: * the buckets' simple locks give us atomicity. */
311: *(unsigned int *)addr = val;
312:
313: vm_map_unlock_read (task->map);
314:
315: int found = 0;
316: struct list *runp = gsync_find_key (&hbp->entries, &key, &found);
317: if (found)
318: {
319: do
320: runp = dequeue_waiter (runp);
321: while ((flags & GSYNC_BROADCAST) &&
322: !list_end (&hbp->entries, runp) &&
323: gsync_key_eq (&node_to_waiter(runp)->key, &key));
324:
325: ret = KERN_SUCCESS;
326: }
327:
328: simple_unlock (&hbp->lock);
329: return (ret);
330: }
331:
332: kern_return_t gsync_requeue (task_t task, vm_offset_t src,
333: vm_offset_t dst, boolean_t wake_one, int flags)
334: {
1.1.1.2 ! root 335: if (unlikely (task != current_task()))
! 336: /* Not implemented yet. */
! 337: return (KERN_FAILURE);
! 338:
1.1 root 339: struct gsync_key src_k, dst_k;
340: int src_bkt = gsync_fill_key (task, src, flags, &src_k);
341: int dst_bkt = gsync_fill_key (task, dst, flags, &dst_k);
342:
343: if ((src_bkt | dst_bkt) < 0)
344: return (KERN_INVALID_ADDRESS);
345:
346: vm_map_lock_read (task->map);
347:
348: /* We don't actually dereference or modify the contents
349: * of the addresses, but we still check that they can
350: * be accessed by the task. */
351: if (unlikely (!valid_access_p (task->map, src, flags) ||
352: !valid_access_p (task->map, dst, flags)))
353: {
354: vm_map_unlock_read (task->map);
355: return (KERN_INVALID_ADDRESS);
356: }
357:
358: vm_map_unlock_read (task->map);
359:
360: /* If we're asked to unconditionally wake up a waiter, then
361: * we need to remove a maximum of two threads from the queue. */
362: unsigned int nw = 1 + wake_one;
363: struct gsync_hbucket *bp1 = gsync_buckets + src_bkt;
364: struct gsync_hbucket *bp2 = gsync_buckets + dst_bkt;
365:
366: /* Acquire the locks in order, to prevent any potential deadlock. */
367: if (bp1 == bp2)
368: simple_lock (&bp1->lock);
369: else if ((unsigned long)bp1 < (unsigned long)bp2)
370: {
371: simple_lock (&bp1->lock);
372: simple_lock (&bp2->lock);
373: }
374: else
375: {
376: simple_lock (&bp2->lock);
377: simple_lock (&bp1->lock);
378: }
379:
380: kern_return_t ret = KERN_SUCCESS;
381: int exact;
382: struct list *inp = gsync_find_key (&bp1->entries, &src_k, &exact);
383:
384: if (!exact)
385: /* There are no waiters in the source queue. */
386: ret = KERN_INVALID_ARGUMENT;
387: else
388: {
389: struct list *outp = gsync_find_key (&bp2->entries, &dst_k, 0);
390:
391: /* We're going to need a node that points one past the
392: * end of the waiters in the source queue. */
393: struct list *endp = inp;
394:
395: do
396: {
397: /* Modify the keys while iterating. */
398: node_to_waiter(endp)->key = dst_k;
399: endp = list_next (endp);
400: }
401: while (((flags & GSYNC_BROADCAST) || --nw != 0) &&
402: !list_end (&bp1->entries, endp) &&
403: gsync_key_eq (&node_to_waiter(endp)->key, &src_k));
404:
405: /* Splice the list by removing waiters from the source queue
406: * and inserting them into the destination queue. */
407: inp->prev->next = endp;
408: endp->prev->next = outp->next;
409: endp->prev = inp->prev;
410:
411: outp->next = inp;
412: inp->prev = outp;
413:
414: if (wake_one)
415: (void)dequeue_waiter (inp);
416: }
417:
418: /* Release the locks and we're done.*/
419: simple_unlock (&bp1->lock);
420: if (bp1 != bp2)
421: simple_unlock (&bp2->lock);
422:
423: return (ret);
424: }
425:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.