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
  29 #ifndef __FUTEX_MAP_HH__
  30 #define __FUTEX_MAP_HH__
  31
  32 #include <unordered_map>
  33
  34 #include <cpu/thread_context.hh>
  35
  36 /**
  37  * FutexKey class defines an unique identifier for a particular futex in the
  38  * system. The tgid and an address are the unique values needed as the key.
  39  */
  40 class FutexKey {
  41   public:
  42     uint64_t addr;
  43     uint64_t tgid;
  44
  45     FutexKey(uint64_t addr_in, uint64_t tgid_in)
  46         : addr(addr_in), tgid(tgid_in)
  47     {
  48     }
  49
  50     bool
  51     operator==(const FutexKey &in) const
  52     {
  53         return addr == in.addr && tgid == in.tgid;
  54     }
  55 };
  56
  57 namespace std {
  58     /**
  59      * The unordered_map structure needs the parenthesis operator defined for
  60      * std::hash if a user defined key is used. Our key is is user defined
  61      * so we need to provide the hash functor.
  62      */
  63     template <>
  64     struct hash<FutexKey>
  65     {
  66         size_t operator()(const FutexKey& in) const
  67         {
  68             size_t hash = 65521;
  69             for (int i = 0; i < sizeof(uint64_t) / sizeof(size_t); i++) {
  70                 hash ^= (size_t)(in.addr >> sizeof(size_t) * i) ^
  71                         (size_t)(in.tgid >> sizeof(size_t) * i);
  72             }
  73             return hash;
  74         }
  75     };
  76 }
  77
  78 /**
  79  * WaiterState defines internal state of a waiter thread. The state
  80  * includes a pointer to the thread's context and its associated bitmask.
  81  */
  82 class WaiterState {
  83   public:
  84     ThreadContext* tc;
  85     int bitmask;
  86
  87     /**
  88      * this constructor is used if futex ops with bitset are used
  89      */
  90     WaiterState(ThreadContext* _tc, int _bitmask)
  91       : tc(_tc), bitmask(_bitmask)
  92     { }
  93
  94     /**
  95      * if bitset is not defined, just set bitmask to 0xffffffff
  96      */
  97     WaiterState(ThreadContext* _tc)
  98       : tc(_tc), bitmask(0xffffffff)
  99     { }
 100
 101     /**
 102      * return true if the bit-wise AND of the wakeup_bitmask given by
 103      * a waking thread and this thread's internal bitmask is non-zero
 104      */
 105     bool
 106     checkMask(int wakeup_bitmask) const
 107     {
 108         return bitmask & wakeup_bitmask;
 109     }
 110 };
 111
 112 typedef std::list<WaiterState> WaiterList;
 113
 114 /**
 115  * FutexMap class holds a map of all futexes used in the system
 116  */
 117 class FutexMap : public std::unordered_map<FutexKey, WaiterList>
 118 {
 119   public:
 120     /** Inserts a futex into the map with one waiting TC */
 121     void
 122     suspend(Addr addr, uint64_t tgid, ThreadContext *tc)
 123     {
 124         FutexKey key(addr, tgid);
 125         auto it = find(key);
 126
 127         if (it == end()) {
 128             WaiterList waiterList {WaiterState(tc)};
 129             insert({key, waiterList});
 130         } else {
 131             it->second.push_back(WaiterState(tc));
 132         }
 133
 134         /** Suspend the thread context */
 135         tc->suspend();
 136     }
 137
 138     /** Wakes up at most count waiting threads on a futex */
 139     int
 140     wakeup(Addr addr, uint64_t tgid, int count)
 141     {
 142         FutexKey key(addr, tgid);
 143         auto it = find(key);
 144
 145         if (it == end())
 146             return 0;
 147
 148         int woken_up = 0;
 149         auto &waiterList = it->second;
 150
 151         while (!waiterList.empty() && woken_up < count) {
 152             // Threads may be woken up by access to locked
 153             // memory addresses outside of syscalls, so we
 154             // must only count threads that were actually
 155             // woken up by this syscall.
 156             auto& tc = waiterList.front().tc;
 157             if (tc->status() == ThreadContext::Suspended) {
 158                 tc->activate();
 159                 woken_up++;
 160             }
 161             waiterList.pop_front();
 162         }
 163
 164         if (waiterList.empty())
 165             erase(it);
 166
 167         return woken_up;
 168     }
 169
 170     /**
 171      * inserts a futex into the map with one waiting TC
 172      * associates the waiter with a given bitmask
 173      */
 174     void
 175     suspend_bitset(Addr addr, uint64_t tgid, ThreadContext *tc,
 176                    int bitmask)
 177     {
 178         FutexKey key(addr, tgid);
 179         auto it = find(key);
 180
 181         if (it == end()) {
 182             WaiterList waiterList {WaiterState(tc, bitmask)};
 183             insert({key, waiterList});
 184         } else {
 185             it->second.push_back(WaiterState(tc, bitmask));
 186         }
 187
 188         /** Suspend the thread context */
 189         tc->suspend();
 190     }
 191
 192     /**
 193      * Wakes up all waiters waiting on the addr and associated with the
 194      * given bitset
 195      */
 196     int
 197     wakeup_bitset(Addr addr, uint64_t tgid, int bitmask)
 198     {
 199         FutexKey key(addr, tgid);
 200         auto it = find(key);
 201
 202         if (it == end())
 203             return 0;
 204
 205         int woken_up = 0;
 206
 207         auto &waiterList = it->second;
 208         auto iter = waiterList.begin();
 209
 210         while (iter != waiterList.end()) {
 211             WaiterState& waiter = *iter;
 212
 213             if (waiter.checkMask(bitmask)) {
 214                 waiter.tc->activate();
 215                 iter = waiterList.erase(iter);
 216                 woken_up++;
 217             } else {
 218                 ++iter;
 219             }
 220         }
 221
 222         if (waiterList.empty())
 223             erase(it);
 224
 225         return woken_up;
 226     }
 227
 228     /**
 229      * This operation wakes a given number (val) of waiters. If there are
 230      * more threads waiting than woken, they are removed from the wait
 231      * queue of the futex pointed to by addr1 and added to the wait queue
 232      * of the futex pointed to by addr2. The number of waiter moved is
 233      * capped by count2 (misused timeout parameter).
 234      *
 235      * The return value is the number of waiters that are woken or
 236      * requeued.
 237      */
 238     int
 239     requeue(Addr addr1, uint64_t tgid, int count, int count2, Addr addr2)
 240     {
 241         FutexKey key1(addr1, tgid);
 242         auto it1 = find(key1);
 243
 244         if (it1 == end())
 245             return 0;
 246
 247         int woken_up = 0;
 248         auto &waiterList1 = it1->second;
 249
 250         while (!waiterList1.empty() && woken_up < count) {
 251             waiterList1.front().tc->activate();
 252             waiterList1.pop_front();
 253             woken_up++;
 254         }
 255
 256         WaiterList tmpList;
 257         int requeued = 0;
 258
 259         while (!waiterList1.empty() && requeued < count2) {
 260           auto w = waiterList1.front();
 261           waiterList1.pop_front();
 262           tmpList.push_back(w);
 263           requeued++;
 264         }
 265
 266         FutexKey key2(addr2, tgid);
 267         auto it2 = find(key2);
 268
 269         if (it2 == end() && requeued > 0) {
 270             insert({key2, tmpList});
 271         } else {
 272             it2->second.insert(it2->second.end(),
 273                                tmpList.begin(), tmpList.end());
 274         }
 275
 276         if (waiterList1.empty())
 277             erase(it1);
 278
 279         return woken_up + requeued;
 280     }
 281 };
 282
 283 #endif // __FUTEX_MAP_HH__