futex_map.hh revision 13650
111911SBrandon.Potter@amd.com/* 211911SBrandon.Potter@amd.com * Copyright (c) 2017 Advanced Micro Devices, Inc. 311911SBrandon.Potter@amd.com * All rights reserved. 411911SBrandon.Potter@amd.com * 511911SBrandon.Potter@amd.com * Redistribution and use in source and binary forms, with or without 611911SBrandon.Potter@amd.com * modification, are permitted provided that the following conditions are 711911SBrandon.Potter@amd.com * met: redistributions of source code must retain the above copyright 811911SBrandon.Potter@amd.com * notice, this list of conditions and the following disclaimer; 911911SBrandon.Potter@amd.com * redistributions in binary form must reproduce the above copyright 1011911SBrandon.Potter@amd.com * notice, this list of conditions and the following disclaimer in the 1111911SBrandon.Potter@amd.com * documentation and/or other materials provided with the distribution; 1211911SBrandon.Potter@amd.com * neither the name of the copyright holders nor the names of its 1311911SBrandon.Potter@amd.com * contributors may be used to endorse or promote products derived from 1411911SBrandon.Potter@amd.com * this software without specific prior written permission. 1511911SBrandon.Potter@amd.com * 1611911SBrandon.Potter@amd.com * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1711911SBrandon.Potter@amd.com * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1811911SBrandon.Potter@amd.com * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1911911SBrandon.Potter@amd.com * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2011911SBrandon.Potter@amd.com * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2111911SBrandon.Potter@amd.com * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2211911SBrandon.Potter@amd.com * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2311911SBrandon.Potter@amd.com * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2411911SBrandon.Potter@amd.com * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2511911SBrandon.Potter@amd.com * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2611911SBrandon.Potter@amd.com * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2711911SBrandon.Potter@amd.com * 2811911SBrandon.Potter@amd.com * Authors: Brandon Potter 2911911SBrandon.Potter@amd.com * Steve Reinhardt 3011911SBrandon.Potter@amd.com * Alexandru Dutu 3111911SBrandon.Potter@amd.com */ 3211911SBrandon.Potter@amd.com 3311911SBrandon.Potter@amd.com#ifndef __FUTEX_MAP_HH__ 3411911SBrandon.Potter@amd.com#define __FUTEX_MAP_HH__ 3511911SBrandon.Potter@amd.com 3611911SBrandon.Potter@amd.com#include <unordered_map> 3711911SBrandon.Potter@amd.com 3811911SBrandon.Potter@amd.com#include <cpu/thread_context.hh> 3911911SBrandon.Potter@amd.com 4011911SBrandon.Potter@amd.com/** 4111911SBrandon.Potter@amd.com * FutexKey class defines an unique identifier for a particular futex in the 4211911SBrandon.Potter@amd.com * system. The tgid and an address are the unique values needed as the key. 4311911SBrandon.Potter@amd.com */ 4411911SBrandon.Potter@amd.comclass FutexKey { 4511911SBrandon.Potter@amd.com public: 4611911SBrandon.Potter@amd.com uint64_t addr; 4711911SBrandon.Potter@amd.com uint64_t tgid; 4811911SBrandon.Potter@amd.com 4911911SBrandon.Potter@amd.com FutexKey(uint64_t addr_in, uint64_t tgid_in) 5011911SBrandon.Potter@amd.com : addr(addr_in), tgid(tgid_in) 5111911SBrandon.Potter@amd.com { 5211911SBrandon.Potter@amd.com } 5311911SBrandon.Potter@amd.com 5411911SBrandon.Potter@amd.com bool 5511911SBrandon.Potter@amd.com operator==(const FutexKey &in) const 5611911SBrandon.Potter@amd.com { 5711911SBrandon.Potter@amd.com return addr == in.addr && tgid == in.tgid; 5811911SBrandon.Potter@amd.com } 5911911SBrandon.Potter@amd.com}; 6011911SBrandon.Potter@amd.com 6111911SBrandon.Potter@amd.comnamespace std { 6211911SBrandon.Potter@amd.com /** 6311911SBrandon.Potter@amd.com * The unordered_map structure needs the parenthesis operator defined for 6411911SBrandon.Potter@amd.com * std::hash if a user defined key is used. Our key is is user defined 6511911SBrandon.Potter@amd.com * so we need to provide the hash functor. 6611911SBrandon.Potter@amd.com */ 6711911SBrandon.Potter@amd.com template <> 6811911SBrandon.Potter@amd.com struct hash<FutexKey> 6911911SBrandon.Potter@amd.com { 7011911SBrandon.Potter@amd.com size_t operator()(const FutexKey& in) const 7111911SBrandon.Potter@amd.com { 7211911SBrandon.Potter@amd.com size_t hash = 65521; 7311911SBrandon.Potter@amd.com for (int i = 0; i < sizeof(uint64_t) / sizeof(size_t); i++) { 7411911SBrandon.Potter@amd.com hash ^= (size_t)(in.addr >> sizeof(size_t) * i) ^ 7511911SBrandon.Potter@amd.com (size_t)(in.tgid >> sizeof(size_t) * i); 7611911SBrandon.Potter@amd.com } 7711911SBrandon.Potter@amd.com return hash; 7811911SBrandon.Potter@amd.com } 7911911SBrandon.Potter@amd.com }; 8011911SBrandon.Potter@amd.com} 8111911SBrandon.Potter@amd.com 8213642Sqtt2@cornell.edu/** 8313642Sqtt2@cornell.edu * WaiterState defines internal state of a waiter thread. The state 8413642Sqtt2@cornell.edu * includes a pointer to the thread's context and its associated bitmask. 8513642Sqtt2@cornell.edu */ 8613642Sqtt2@cornell.educlass WaiterState { 8713642Sqtt2@cornell.edu public: 8813642Sqtt2@cornell.edu ThreadContext* tc; 8913642Sqtt2@cornell.edu int bitmask; 9013642Sqtt2@cornell.edu 9113642Sqtt2@cornell.edu /** 9213642Sqtt2@cornell.edu * this constructor is used if futex ops with bitset are used 9313642Sqtt2@cornell.edu */ 9413642Sqtt2@cornell.edu WaiterState(ThreadContext* _tc, int _bitmask) 9513642Sqtt2@cornell.edu : tc(_tc), bitmask(_bitmask) 9613642Sqtt2@cornell.edu { } 9713642Sqtt2@cornell.edu 9813642Sqtt2@cornell.edu /** 9913642Sqtt2@cornell.edu * if bitset is not defined, just set bitmask to 0xffffffff 10013642Sqtt2@cornell.edu */ 10113642Sqtt2@cornell.edu WaiterState(ThreadContext* _tc) 10213642Sqtt2@cornell.edu : tc(_tc), bitmask(0xffffffff) 10313642Sqtt2@cornell.edu { } 10413642Sqtt2@cornell.edu 10513642Sqtt2@cornell.edu /** 10613642Sqtt2@cornell.edu * return true if the bit-wise AND of the wakeup_bitmask given by 10713642Sqtt2@cornell.edu * a waking thread and this thread's internal bitmask is non-zero 10813642Sqtt2@cornell.edu */ 10913642Sqtt2@cornell.edu bool 11013642Sqtt2@cornell.edu checkMask(int wakeup_bitmask) const 11113642Sqtt2@cornell.edu { 11213642Sqtt2@cornell.edu return bitmask & wakeup_bitmask; 11313642Sqtt2@cornell.edu } 11413642Sqtt2@cornell.edu}; 11513642Sqtt2@cornell.edu 11613642Sqtt2@cornell.edutypedef std::list<WaiterState> WaiterList; 11711911SBrandon.Potter@amd.com 11811911SBrandon.Potter@amd.com/** 11911911SBrandon.Potter@amd.com * FutexMap class holds a map of all futexes used in the system 12011911SBrandon.Potter@amd.com */ 12113642Sqtt2@cornell.educlass FutexMap : public std::unordered_map<FutexKey, WaiterList> 12211911SBrandon.Potter@amd.com{ 12311911SBrandon.Potter@amd.com public: 12411911SBrandon.Potter@amd.com /** Inserts a futex into the map with one waiting TC */ 12511911SBrandon.Potter@amd.com void 12611911SBrandon.Potter@amd.com suspend(Addr addr, uint64_t tgid, ThreadContext *tc) 12711911SBrandon.Potter@amd.com { 12811911SBrandon.Potter@amd.com FutexKey key(addr, tgid); 12911911SBrandon.Potter@amd.com auto it = find(key); 13011911SBrandon.Potter@amd.com 13111911SBrandon.Potter@amd.com if (it == end()) { 13213642Sqtt2@cornell.edu WaiterList waiterList {WaiterState(tc)}; 13313642Sqtt2@cornell.edu insert({key, waiterList}); 13411911SBrandon.Potter@amd.com } else { 13513642Sqtt2@cornell.edu it->second.push_back(WaiterState(tc)); 13611911SBrandon.Potter@amd.com } 13711911SBrandon.Potter@amd.com 13811911SBrandon.Potter@amd.com /** Suspend the thread context */ 13911911SBrandon.Potter@amd.com tc->suspend(); 14011911SBrandon.Potter@amd.com } 14111911SBrandon.Potter@amd.com 14211911SBrandon.Potter@amd.com /** Wakes up at most count waiting threads on a futex */ 14311911SBrandon.Potter@amd.com int 14411911SBrandon.Potter@amd.com wakeup(Addr addr, uint64_t tgid, int count) 14511911SBrandon.Potter@amd.com { 14611911SBrandon.Potter@amd.com FutexKey key(addr, tgid); 14711911SBrandon.Potter@amd.com auto it = find(key); 14811911SBrandon.Potter@amd.com 14911911SBrandon.Potter@amd.com if (it == end()) 15011911SBrandon.Potter@amd.com return 0; 15111911SBrandon.Potter@amd.com 15211911SBrandon.Potter@amd.com int woken_up = 0; 15313642Sqtt2@cornell.edu auto &waiterList = it->second; 15411911SBrandon.Potter@amd.com 15513642Sqtt2@cornell.edu while (!waiterList.empty() && woken_up < count) { 15613642Sqtt2@cornell.edu waiterList.front().tc->activate(); 15713642Sqtt2@cornell.edu waiterList.pop_front(); 15811911SBrandon.Potter@amd.com woken_up++; 15911911SBrandon.Potter@amd.com } 16011911SBrandon.Potter@amd.com 16113642Sqtt2@cornell.edu if (waiterList.empty()) 16211911SBrandon.Potter@amd.com erase(it); 16311911SBrandon.Potter@amd.com 16411911SBrandon.Potter@amd.com return woken_up; 16511911SBrandon.Potter@amd.com } 16611911SBrandon.Potter@amd.com 16713642Sqtt2@cornell.edu /** 16813642Sqtt2@cornell.edu * inserts a futex into the map with one waiting TC 16913642Sqtt2@cornell.edu * associates the waiter with a given bitmask 17013642Sqtt2@cornell.edu */ 17113642Sqtt2@cornell.edu void 17213642Sqtt2@cornell.edu suspend_bitset(Addr addr, uint64_t tgid, ThreadContext *tc, 17313642Sqtt2@cornell.edu int bitmask) 17413642Sqtt2@cornell.edu { 17513642Sqtt2@cornell.edu FutexKey key(addr, tgid); 17613642Sqtt2@cornell.edu auto it = find(key); 17713642Sqtt2@cornell.edu 17813642Sqtt2@cornell.edu if (it == end()) { 17913642Sqtt2@cornell.edu WaiterList waiterList {WaiterState(tc, bitmask)}; 18013642Sqtt2@cornell.edu insert({key, waiterList}); 18113642Sqtt2@cornell.edu } else { 18213642Sqtt2@cornell.edu it->second.push_back(WaiterState(tc, bitmask)); 18313642Sqtt2@cornell.edu } 18413642Sqtt2@cornell.edu 18513642Sqtt2@cornell.edu /** Suspend the thread context */ 18613642Sqtt2@cornell.edu tc->suspend(); 18713642Sqtt2@cornell.edu } 18813642Sqtt2@cornell.edu 18913642Sqtt2@cornell.edu /** 19013642Sqtt2@cornell.edu * Wakes up all waiters waiting on the addr and associated with the 19113642Sqtt2@cornell.edu * given bitset 19213642Sqtt2@cornell.edu */ 19313642Sqtt2@cornell.edu int 19413642Sqtt2@cornell.edu wakeup_bitset(Addr addr, uint64_t tgid, int bitmask) 19513642Sqtt2@cornell.edu { 19613642Sqtt2@cornell.edu FutexKey key(addr, tgid); 19713642Sqtt2@cornell.edu auto it = find(key); 19813642Sqtt2@cornell.edu 19913642Sqtt2@cornell.edu if (it == end()) 20013642Sqtt2@cornell.edu return 0; 20113642Sqtt2@cornell.edu 20213642Sqtt2@cornell.edu int woken_up = 0; 20313642Sqtt2@cornell.edu 20413642Sqtt2@cornell.edu auto &waiterList = it->second; 20513642Sqtt2@cornell.edu auto iter = waiterList.begin(); 20613642Sqtt2@cornell.edu 20713642Sqtt2@cornell.edu while (iter != waiterList.end()) { 20813642Sqtt2@cornell.edu WaiterState& waiter = *iter; 20913642Sqtt2@cornell.edu 21013642Sqtt2@cornell.edu if (waiter.checkMask(bitmask)) { 21113642Sqtt2@cornell.edu waiter.tc->activate(); 21213642Sqtt2@cornell.edu iter = waiterList.erase(iter); 21313642Sqtt2@cornell.edu woken_up++; 21413642Sqtt2@cornell.edu } else { 21513642Sqtt2@cornell.edu ++iter; 21613642Sqtt2@cornell.edu } 21713642Sqtt2@cornell.edu } 21813642Sqtt2@cornell.edu 21913642Sqtt2@cornell.edu if (waiterList.empty()) 22013642Sqtt2@cornell.edu erase(it); 22113642Sqtt2@cornell.edu 22213642Sqtt2@cornell.edu return woken_up; 22313642Sqtt2@cornell.edu } 22413650Smw828@cornell.edu 22513650Smw828@cornell.edu /** 22613650Smw828@cornell.edu * This operation wakes a given number (val) of waiters. If there are 22713650Smw828@cornell.edu * more threads waiting than woken, they are removed from the wait 22813650Smw828@cornell.edu * queue of the futex pointed to by addr1 and added to the wait queue 22913650Smw828@cornell.edu * of the futex pointed to by addr2. The number of waiter moved is 23013650Smw828@cornell.edu * capped by count2 (misused timeout parameter). 23113650Smw828@cornell.edu * 23213650Smw828@cornell.edu * The return value is the number of waiters that are woken or 23313650Smw828@cornell.edu * requeued. 23413650Smw828@cornell.edu */ 23513650Smw828@cornell.edu int 23613650Smw828@cornell.edu requeue(Addr addr1, uint64_t tgid, int count, int count2, Addr addr2) 23713650Smw828@cornell.edu { 23813650Smw828@cornell.edu FutexKey key1(addr1, tgid); 23913650Smw828@cornell.edu auto it1 = find(key1); 24013650Smw828@cornell.edu 24113650Smw828@cornell.edu if (it1 == end()) 24213650Smw828@cornell.edu return 0; 24313650Smw828@cornell.edu 24413650Smw828@cornell.edu int woken_up = 0; 24513650Smw828@cornell.edu auto &waiterList1 = it1->second; 24613650Smw828@cornell.edu 24713650Smw828@cornell.edu while (!waiterList1.empty() && woken_up < count) { 24813650Smw828@cornell.edu waiterList1.front().tc->activate(); 24913650Smw828@cornell.edu waiterList1.pop_front(); 25013650Smw828@cornell.edu woken_up++; 25113650Smw828@cornell.edu } 25213650Smw828@cornell.edu 25313650Smw828@cornell.edu WaiterList tmpList; 25413650Smw828@cornell.edu int requeued = 0; 25513650Smw828@cornell.edu 25613650Smw828@cornell.edu while (!waiterList1.empty() && requeued < count2) { 25713650Smw828@cornell.edu auto w = waiterList1.front(); 25813650Smw828@cornell.edu waiterList1.pop_front(); 25913650Smw828@cornell.edu tmpList.push_back(w); 26013650Smw828@cornell.edu requeued++; 26113650Smw828@cornell.edu } 26213650Smw828@cornell.edu 26313650Smw828@cornell.edu FutexKey key2(addr2, tgid); 26413650Smw828@cornell.edu auto it2 = find(key2); 26513650Smw828@cornell.edu 26613650Smw828@cornell.edu if (it2 == end() && requeued > 0) { 26713650Smw828@cornell.edu insert({key2, tmpList}); 26813650Smw828@cornell.edu } else { 26913650Smw828@cornell.edu it2->second.insert(it2->second.end(), 27013650Smw828@cornell.edu tmpList.begin(), tmpList.end()); 27113650Smw828@cornell.edu } 27213650Smw828@cornell.edu 27313650Smw828@cornell.edu if (waiterList1.empty()) 27413650Smw828@cornell.edu erase(it1); 27513650Smw828@cornell.edu 27613650Smw828@cornell.edu return woken_up + requeued; 27713650Smw828@cornell.edu } 27811911SBrandon.Potter@amd.com}; 27911911SBrandon.Potter@amd.com 28011911SBrandon.Potter@amd.com#endif // __FUTEX_MAP_HH__ 281