Return to gsync.c CVS log

Up to [GnuMach] / Gnu-Mach / kern

Annotation of Gnu-Mach/kern/gsync.c, revision 1.1

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.