![[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
7: version 3 of the license, or (at your option) any later version.
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: {
188: struct gsync_waiter w;
189: int bucket = gsync_fill_key (task, addr, flags, &w.key);
190:
191: if (unlikely (bucket < 0))
192: return (KERN_INVALID_ADDRESS);
193:
194: struct gsync_hbucket *hbp = gsync_buckets + bucket;
195: simple_lock (&hbp->lock);
196:
197: /* Now test that the address is actually valid for the
198: * given task. Do so with the read-lock held in order
199: * to prevent memory deallocations. */
200: vm_map_lock_read (task->map);
201:
202: if (unlikely (!valid_access_p (task->map, addr, flags)))
203: {
204: simple_unlock (&hbp->lock);
205: vm_map_unlock_read (task->map);
206: return (KERN_INVALID_ADDRESS);
207: }
208:
209: /* Before doing any work, check that the expected value(s)
210: * match the contents of the address. Otherwise, the waiting
211: * thread could potentially miss a wakeup. */
212: if (((unsigned int *)addr)[0] != lo ||
213: ((flags & GSYNC_QUAD) &&
214: ((unsigned int *)addr)[1] != hi))
215: {
216: simple_unlock (&hbp->lock);
217: vm_map_unlock_read (task->map);
218: return (KERN_INVALID_ARGUMENT);
219: }
220:
221: vm_map_unlock_read (task->map);
222:
223: /* Look for the first entry in the hash bucket that
224: * compares strictly greater than this waiter. */
225: struct list *runp;
226: list_for_each (&hbp->entries, runp)
227: {
228: struct gsync_waiter *p = node_to_waiter (runp);
229: if (gsync_key_lt (&w.key, &p->key))
230: break;
231: }
232:
233: /* Finally, add ourselves to the list and go to sleep. */
234: list_add (runp->prev, runp, &w.link);
235: w.waiter = current_thread ();
236:
237: if (flags & GSYNC_TIMED)
238: thread_will_wait_with_timeout (w.waiter, msec);
239: else
240: thread_will_wait (w.waiter);
241:
242: thread_sleep (0, (simple_lock_t)&hbp->lock, TRUE);
243:
244: /* We're back. */
245: kern_return_t ret = current_thread()->wait_result;
246: if (ret != THREAD_AWAKENED)
247: {
248: /* We were interrupted or timed out. */
249: simple_lock (&hbp->lock);
250: if (w.link.next != 0)
251: list_remove (&w.link);
252: simple_unlock (&hbp->lock);
253:
254: /* Map the error code. */
255: ret = ret == THREAD_INTERRUPTED ?
256: KERN_INTERRUPTED : KERN_TIMEDOUT;
257: }
258: else
259: ret = KERN_SUCCESS;
260:
261: return (ret);
262: }
263:
264: /* Remove a waiter from the queue, wake it up, and
265: * return the next node. */
266: static inline struct list*
267: dequeue_waiter (struct list *nodep)
268: {
269: struct list *nextp = list_next (nodep);
270: list_remove (nodep);
271: list_node_init (nodep);
272: clear_wait (node_to_waiter(nodep)->waiter,
273: THREAD_AWAKENED, FALSE);
274: return (nextp);
275: }
276:
277: kern_return_t gsync_wake (task_t task,
278: vm_offset_t addr, unsigned int val, int flags)
279: {
280: struct gsync_key key;
281: int bucket = gsync_fill_key (task, addr, flags, &key);
282:
283: if (unlikely (bucket < 0))
284: return (KERN_INVALID_ADDRESS);
285:
286: kern_return_t ret = KERN_INVALID_ARGUMENT;
287:
288: struct gsync_hbucket *hbp = gsync_buckets + bucket;
289: simple_lock (&hbp->lock);
290: vm_map_lock_read (task->map);
291:
292: if (unlikely (!valid_access_p (task->map, addr, flags)))
293: {
294: simple_unlock (&hbp->lock);
295: vm_map_unlock_read (task->map);
296: return (KERN_INVALID_ADDRESS);
297: }
298:
299: if (flags & GSYNC_MUTATE)
300: /* Set the contents of the address to the specified value,
301: * even if we don't end up waking any threads. Note that
302: * the buckets' simple locks give us atomicity. */
303: *(unsigned int *)addr = val;
304:
305: vm_map_unlock_read (task->map);
306:
307: int found = 0;
308: struct list *runp = gsync_find_key (&hbp->entries, &key, &found);
309: if (found)
310: {
311: do
312: runp = dequeue_waiter (runp);
313: while ((flags & GSYNC_BROADCAST) &&
314: !list_end (&hbp->entries, runp) &&
315: gsync_key_eq (&node_to_waiter(runp)->key, &key));
316:
317: ret = KERN_SUCCESS;
318: }
319:
320: simple_unlock (&hbp->lock);
321: return (ret);
322: }
323:
324: kern_return_t gsync_requeue (task_t task, vm_offset_t src,
325: vm_offset_t dst, boolean_t wake_one, int flags)
326: {
327: struct gsync_key src_k, dst_k;
328: int src_bkt = gsync_fill_key (task, src, flags, &src_k);
329: int dst_bkt = gsync_fill_key (task, dst, flags, &dst_k);
330:
331: if ((src_bkt | dst_bkt) < 0)
332: return (KERN_INVALID_ADDRESS);
333:
334: vm_map_lock_read (task->map);
335:
336: /* We don't actually dereference or modify the contents
337: * of the addresses, but we still check that they can
338: * be accessed by the task. */
339: if (unlikely (!valid_access_p (task->map, src, flags) ||
340: !valid_access_p (task->map, dst, flags)))
341: {
342: vm_map_unlock_read (task->map);
343: return (KERN_INVALID_ADDRESS);
344: }
345:
346: vm_map_unlock_read (task->map);
347:
348: /* If we're asked to unconditionally wake up a waiter, then
349: * we need to remove a maximum of two threads from the queue. */
350: unsigned int nw = 1 + wake_one;
351: struct gsync_hbucket *bp1 = gsync_buckets + src_bkt;
352: struct gsync_hbucket *bp2 = gsync_buckets + dst_bkt;
353:
354: /* Acquire the locks in order, to prevent any potential deadlock. */
355: if (bp1 == bp2)
356: simple_lock (&bp1->lock);
357: else if ((unsigned long)bp1 < (unsigned long)bp2)
358: {
359: simple_lock (&bp1->lock);
360: simple_lock (&bp2->lock);
361: }
362: else
363: {
364: simple_lock (&bp2->lock);
365: simple_lock (&bp1->lock);
366: }
367:
368: kern_return_t ret = KERN_SUCCESS;
369: int exact;
370: struct list *inp = gsync_find_key (&bp1->entries, &src_k, &exact);
371:
372: if (!exact)
373: /* There are no waiters in the source queue. */
374: ret = KERN_INVALID_ARGUMENT;
375: else
376: {
377: struct list *outp = gsync_find_key (&bp2->entries, &dst_k, 0);
378:
379: /* We're going to need a node that points one past the
380: * end of the waiters in the source queue. */
381: struct list *endp = inp;
382:
383: do
384: {
385: /* Modify the keys while iterating. */
386: node_to_waiter(endp)->key = dst_k;
387: endp = list_next (endp);
388: }
389: while (((flags & GSYNC_BROADCAST) || --nw != 0) &&
390: !list_end (&bp1->entries, endp) &&
391: gsync_key_eq (&node_to_waiter(endp)->key, &src_k));
392:
393: /* Splice the list by removing waiters from the source queue
394: * and inserting them into the destination queue. */
395: inp->prev->next = endp;
396: endp->prev->next = outp->next;
397: endp->prev = inp->prev;
398:
399: outp->next = inp;
400: inp->prev = outp;
401:
402: if (wake_one)
403: (void)dequeue_waiter (inp);
404: }
405:
406: /* Release the locks and we're done.*/
407: simple_unlock (&bp1->lock);
408: if (bp1 != bp2)
409: simple_unlock (&bp2->lock);
410:
411: return (ret);
412: }
413:
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.