futex_map.hh revision 11911 
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
82typedef std::list<ThreadContext *> ThreadContextList;
83
84/**
85 * FutexMap class holds a map of all futexes used in the system
86 */
87class 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__
136