src/sim/futex_map.hh

   1 /*
   2  * Copyright (c) 2017 Advanced Micro Devices, Inc.
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met: redistributions of source code must retain the above copyright
   8  * notice, this list of conditions and the following disclaimer;
   9  * redistributions in binary form must reproduce the above copyright
  10  * notice, this list of conditions and the following disclaimer in the
  11  * documentation and/or other materials provided with the distribution;
  12  * neither the name of the copyright holders nor the names of its
  13  * contributors may be used to endorse or promote products derived from
  14  * this software without specific prior written permission.
  15  *
  16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  17  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  18  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  19  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  20  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  21  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  22  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  23  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  24  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  27  *
  28  * Authors: Brandon Potter
  29  *          Steve Reinhardt
  30  *          Alexandru Dutu
  31  */
  32
  33 #ifndef __FUTEX_MAP_HH__
  34 #define __FUTEX_MAP_HH__
  35
  36 #include <unordered_map>
  37
  38 #include <cpu/thread_context.hh>
  39
  40 /**
  41  * FutexKey class defines an unique identifier for a particular futex in the
  42  * system. The tgid and an address are the unique values needed as the key.
  43  */
  44 class FutexKey {
  45   public:
  46     uint64_t addr;
  47     uint64_t tgid;
  48
  49     FutexKey(uint64_t addr_in, uint64_t tgid_in)
  50         : addr(addr_in), tgid(tgid_in)
  51     {
  52     }
  53
  54     bool
  55     operator==(const FutexKey &in) const
  56     {
  57         return addr == in.addr && tgid == in.tgid;
  58     }
  59 };
  60
  61 namespace std {
  62     /**
  63      * The unordered_map structure needs the parenthesis operator defined for
  64      * std::hash if a user defined key is used. Our key is is user defined
  65      * so we need to provide the hash functor.
  66      */
  67     template <>
  68     struct hash<FutexKey>
  69     {
  70         size_t operator()(const FutexKey& in) const
  71         {
  72             size_t hash = 65521;
  73             for (int i = 0; i < sizeof(uint64_t) / sizeof(size_t); i++) {
  74                 hash ^= (size_t)(in.addr >> sizeof(size_t) * i) ^
  75                         (size_t)(in.tgid >> sizeof(size_t) * i);
  76             }
  77             return hash;
  78         }
  79     };
  80 }
  81
  82 typedef std::list<ThreadContext *> ThreadContextList;
  83
  84 /**
  85  * FutexMap class holds a map of all futexes used in the system
  86  */
  87 class FutexMap : public std::unordered_map<FutexKey, ThreadContextList>
  88 {
  89   public:
  90     /** Inserts a futex into the map with one waiting TC */
  91     void
  92     suspend(Addr addr, uint64_t tgid, ThreadContext *tc)
  93     {
  94         FutexKey key(addr, tgid);
  95         auto it = find(key);
  96
  97         if (it == end()) {
  98             ThreadContextList tcList {tc};
  99             insert({key, tcList});
 100         } else {
 101             it->second.push_back(tc);
 102         }
 103
 104         /** Suspend the thread context */
 105         tc->suspend();
 106     }
 107
 108     /** Wakes up at most count waiting threads on a futex */
 109     int
 110     wakeup(Addr addr, uint64_t tgid, int count)
 111     {
 112         FutexKey key(addr, tgid);
 113         auto it = find(key);
 114
 115         if (it == end())
 116             return 0;
 117
 118         int woken_up = 0;
 119         auto &tcList = it->second;
 120
 121         while (!tcList.empty() && woken_up < count) {
 122             tcList.front()->activate();
 123             tcList.pop_front();
 124             woken_up++;
 125         }
 126
 127         if (tcList.empty())
 128             erase(it);
 129
 130         return woken_up;
 131     }
 132
 133 };
 134
 135 #endif // __FUTEX_MAP_HH__