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 */
44class 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
61namespace 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/**
83 * WaiterState defines internal state of a waiter thread. The state
84 * includes a pointer to the thread's context and its associated bitmask.
85 */
86class WaiterState {
87 public:
88 ThreadContext* tc;
89 int bitmask;
90
91 /**
92 * this constructor is used if futex ops with bitset are used
93 */
94 WaiterState(ThreadContext* _tc, int _bitmask)
95 : tc(_tc), bitmask(_bitmask)
96 { }
97
98 /**
99 * if bitset is not defined, just set bitmask to 0xffffffff
100 */
101 WaiterState(ThreadContext* _tc)
102 : tc(_tc), bitmask(0xffffffff)
103 { }
104
105 /**
106 * return true if the bit-wise AND of the wakeup_bitmask given by
107 * a waking thread and this thread's internal bitmask is non-zero
108 */
109 bool
110 checkMask(int wakeup_bitmask) const
111 {
112 return bitmask & wakeup_bitmask;
113 }
114};
115
116typedef std::list<WaiterState> WaiterList;
117
118/**
119 * FutexMap class holds a map of all futexes used in the system
120 */
121class FutexMap : public std::unordered_map<FutexKey, WaiterList>
122{
123 public:
124 /** Inserts a futex into the map with one waiting TC */
125 void
126 suspend(Addr addr, uint64_t tgid, ThreadContext *tc)
127 {
128 FutexKey key(addr, tgid);
129 auto it = find(key);
130
131 if (it == end()) {
132 WaiterList waiterList {WaiterState(tc)};
133 insert({key, waiterList});
134 } else {
135 it->second.push_back(WaiterState(tc));
136 }
137
138 /** Suspend the thread context */
139 tc->suspend();
140 }
141
142 /** Wakes up at most count waiting threads on a futex */
143 int
144 wakeup(Addr addr, uint64_t tgid, int count)
145 {
146 FutexKey key(addr, tgid);
147 auto it = find(key);
148
149 if (it == end())
150 return 0;
151
152 int woken_up = 0;
153 auto &waiterList = it->second;
154
155 while (!waiterList.empty() && woken_up < count) {
156 waiterList.front().tc->activate();
157 waiterList.pop_front();
158 woken_up++;
159 }
160
161 if (waiterList.empty())
162 erase(it);
163
164 return woken_up;
165 }
166
167 /**
168 * inserts a futex into the map with one waiting TC
169 * associates the waiter with a given bitmask
170 */
171 void
172 suspend_bitset(Addr addr, uint64_t tgid, ThreadContext *tc,
173 int bitmask)
174 {
175 FutexKey key(addr, tgid);
176 auto it = find(key);
177
178 if (it == end()) {
179 WaiterList waiterList {WaiterState(tc, bitmask)};
180 insert({key, waiterList});
181 } else {
182 it->second.push_back(WaiterState(tc, bitmask));
183 }
184
185 /** Suspend the thread context */
186 tc->suspend();
187 }
188
189 /**
190 * Wakes up all waiters waiting on the addr and associated with the
191 * given bitset
192 */
193 int
194 wakeup_bitset(Addr addr, uint64_t tgid, int bitmask)
195 {
196 FutexKey key(addr, tgid);
197 auto it = find(key);
198
199 if (it == end())
200 return 0;
201
202 int woken_up = 0;
203
204 auto &waiterList = it->second;
205 auto iter = waiterList.begin();
206
207 while (iter != waiterList.end()) {
208 WaiterState& waiter = *iter;
209
210 if (waiter.checkMask(bitmask)) {
211 waiter.tc->activate();
212 iter = waiterList.erase(iter);
213 woken_up++;
214 } else {
215 ++iter;
216 }
217 }
218
219 if (waiterList.empty())
220 erase(it);
221
222 return woken_up;
223 }
| 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 */
44class 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
61namespace 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/**
83 * WaiterState defines internal state of a waiter thread. The state
84 * includes a pointer to the thread's context and its associated bitmask.
85 */
86class WaiterState {
87 public:
88 ThreadContext* tc;
89 int bitmask;
90
91 /**
92 * this constructor is used if futex ops with bitset are used
93 */
94 WaiterState(ThreadContext* _tc, int _bitmask)
95 : tc(_tc), bitmask(_bitmask)
96 { }
97
98 /**
99 * if bitset is not defined, just set bitmask to 0xffffffff
100 */
101 WaiterState(ThreadContext* _tc)
102 : tc(_tc), bitmask(0xffffffff)
103 { }
104
105 /**
106 * return true if the bit-wise AND of the wakeup_bitmask given by
107 * a waking thread and this thread's internal bitmask is non-zero
108 */
109 bool
110 checkMask(int wakeup_bitmask) const
111 {
112 return bitmask & wakeup_bitmask;
113 }
114};
115
116typedef std::list<WaiterState> WaiterList;
117
118/**
119 * FutexMap class holds a map of all futexes used in the system
120 */
121class FutexMap : public std::unordered_map<FutexKey, WaiterList>
122{
123 public:
124 /** Inserts a futex into the map with one waiting TC */
125 void
126 suspend(Addr addr, uint64_t tgid, ThreadContext *tc)
127 {
128 FutexKey key(addr, tgid);
129 auto it = find(key);
130
131 if (it == end()) {
132 WaiterList waiterList {WaiterState(tc)};
133 insert({key, waiterList});
134 } else {
135 it->second.push_back(WaiterState(tc));
136 }
137
138 /** Suspend the thread context */
139 tc->suspend();
140 }
141
142 /** Wakes up at most count waiting threads on a futex */
143 int
144 wakeup(Addr addr, uint64_t tgid, int count)
145 {
146 FutexKey key(addr, tgid);
147 auto it = find(key);
148
149 if (it == end())
150 return 0;
151
152 int woken_up = 0;
153 auto &waiterList = it->second;
154
155 while (!waiterList.empty() && woken_up < count) {
156 waiterList.front().tc->activate();
157 waiterList.pop_front();
158 woken_up++;
159 }
160
161 if (waiterList.empty())
162 erase(it);
163
164 return woken_up;
165 }
166
167 /**
168 * inserts a futex into the map with one waiting TC
169 * associates the waiter with a given bitmask
170 */
171 void
172 suspend_bitset(Addr addr, uint64_t tgid, ThreadContext *tc,
173 int bitmask)
174 {
175 FutexKey key(addr, tgid);
176 auto it = find(key);
177
178 if (it == end()) {
179 WaiterList waiterList {WaiterState(tc, bitmask)};
180 insert({key, waiterList});
181 } else {
182 it->second.push_back(WaiterState(tc, bitmask));
183 }
184
185 /** Suspend the thread context */
186 tc->suspend();
187 }
188
189 /**
190 * Wakes up all waiters waiting on the addr and associated with the
191 * given bitset
192 */
193 int
194 wakeup_bitset(Addr addr, uint64_t tgid, int bitmask)
195 {
196 FutexKey key(addr, tgid);
197 auto it = find(key);
198
199 if (it == end())
200 return 0;
201
202 int woken_up = 0;
203
204 auto &waiterList = it->second;
205 auto iter = waiterList.begin();
206
207 while (iter != waiterList.end()) {
208 WaiterState& waiter = *iter;
209
210 if (waiter.checkMask(bitmask)) {
211 waiter.tc->activate();
212 iter = waiterList.erase(iter);
213 woken_up++;
214 } else {
215 ++iter;
216 }
217 }
218
219 if (waiterList.empty())
220 erase(it);
221
222 return woken_up;
223 }
|