blob: 877f5262e9e213cfb4a3c1d867551589dfa52974 [file] [log] [blame]
Achin Gupta4f6ad662013-10-25 09:08:21 +01001/*
Dan Handleye83b0ca2014-01-14 18:17:09 +00002 * Copyright (c) 2013-2014, ARM Limited and Contributors. All rights reserved.
Achin Gupta4f6ad662013-10-25 09:08:21 +01003 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * Redistributions of source code must retain the above copyright notice, this
8 * list of conditions and the following disclaimer.
9 *
10 * Redistributions in binary form must reproduce the above copyright notice,
11 * this list of conditions and the following disclaimer in the documentation
12 * and/or other materials provided with the distribution.
13 *
14 * Neither the name of ARM nor the names of its contributors may be used
15 * to endorse or promote products derived from this software without specific
16 * prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
19 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
20 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
22 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
23 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
24 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
25 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
26 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
27 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
28 * POSSIBILITY OF SUCH DAMAGE.
29 */
30
Dan Handley2bd4ef22014-04-09 13:14:54 +010031#include <arch_helpers.h>
Achin Gupta4f6ad662013-10-25 09:08:21 +010032#include <assert.h>
Achin Gupta4f6ad662013-10-25 09:08:21 +010033#include <bakery_lock.h>
Dan Handleyed6ff952014-05-14 17:44:19 +010034#include <platform.h>
Dan Handley2bd4ef22014-04-09 13:14:54 +010035#include <string.h>
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +000036
37/*
38 * Functions in this file implement Bakery Algorithm for mutual exclusion.
39 *
40 * ARM architecture offers a family of exclusive access instructions to
41 * efficiently implement mutual exclusion with hardware support. However, as
42 * well as depending on external hardware, the these instructions have defined
43 * behavior only on certain memory types (cacheable and Normal memory in
44 * particular; see ARMv8 Architecture Reference Manual section B2.10). Use cases
45 * in trusted firmware are such that mutual exclusion implementation cannot
46 * expect that accesses to the lock have the specific type required by the
47 * architecture for these primitives to function (for example, not all
48 * contenders may have address translation enabled).
49 *
50 * This implementation does not use mutual exclusion primitives. It expects
51 * memory regions where the locks reside to be fully ordered and coherent
52 * (either by disabling address translation, or by assigning proper attributes
53 * when translation is enabled).
54 *
55 * Note that the ARM architecture guarantees single-copy atomicity for aligned
56 * accesses regardless of status of address translation.
57 */
Achin Gupta4f6ad662013-10-25 09:08:21 +010058
59#define assert_bakery_entry_valid(entry, bakery) do { \
60 assert(bakery); \
61 assert(entry < BAKERY_LOCK_MAX_CPUS); \
Dan Handleya70615f2014-04-09 12:48:25 +010062} while (0)
Achin Gupta4f6ad662013-10-25 09:08:21 +010063
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +000064/* Convert a ticket to priority */
65#define PRIORITY(t, pos) (((t) << 8) | (pos))
66
67
68/* Initialize Bakery Lock to reset ownership and all ticket values */
Dan Handleye2712bc2014-04-10 15:37:22 +010069void bakery_lock_init(bakery_lock_t *bakery)
Achin Gupta4f6ad662013-10-25 09:08:21 +010070{
71 assert(bakery);
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +000072
73 /* All ticket values need to be 0 */
Achin Gupta4f6ad662013-10-25 09:08:21 +010074 memset(bakery, 0, sizeof(*bakery));
75 bakery->owner = NO_OWNER;
76}
77
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +000078
79/* Obtain a ticket for a given CPU */
Dan Handleye2712bc2014-04-10 15:37:22 +010080static unsigned int bakery_get_ticket(bakery_lock_t *bakery, unsigned int me)
Achin Gupta4f6ad662013-10-25 09:08:21 +010081{
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +000082 unsigned int my_ticket, their_ticket;
83 unsigned int they;
Achin Gupta4f6ad662013-10-25 09:08:21 +010084
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +000085 /*
86 * Flag that we're busy getting our ticket. All CPUs are iterated in the
87 * order of their ordinal position to decide the maximum ticket value
88 * observed so far. Our priority is set to be greater than the maximum
89 * observed priority
90 *
91 * Note that it's possible that more than one contender gets the same
92 * ticket value. That's OK as the lock is acquired based on the priority
93 * value, not the ticket value alone.
94 */
95 my_ticket = 0;
96 bakery->entering[me] = 1;
97 for (they = 0; they < BAKERY_LOCK_MAX_CPUS; they++) {
98 their_ticket = bakery->number[they];
99 if (their_ticket > my_ticket)
100 my_ticket = their_ticket;
101 }
Achin Gupta4f6ad662013-10-25 09:08:21 +0100102
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000103 /*
104 * Compute ticket; then signal to other contenders waiting for us to
105 * finish calculating our ticket value that we're done
106 */
107 ++my_ticket;
108 bakery->number[me] = my_ticket;
109 bakery->entering[me] = 0;
110 sev();
Achin Gupta4f6ad662013-10-25 09:08:21 +0100111
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000112 return my_ticket;
113}
Achin Gupta4f6ad662013-10-25 09:08:21 +0100114
Achin Gupta4f6ad662013-10-25 09:08:21 +0100115
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000116/*
117 * Acquire bakery lock
118 *
119 * Contending CPUs need first obtain a non-zero ticket and then calculate
120 * priority value. A contending CPU iterate over all other CPUs in the platform,
121 * which may be contending for the same lock, in the order of their ordinal
122 * position (CPU0, CPU1 and so on). A non-contending CPU will have its ticket
123 * (and priority) value as 0. The contending CPU compares its priority with that
124 * of others'. The CPU with the highest priority (lowest numerical value)
125 * acquires the lock
126 */
Andrew Thoelke958cc022014-06-09 12:54:15 +0100127void bakery_lock_get(bakery_lock_t *bakery)
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000128{
129 unsigned int they, me;
130 unsigned int my_ticket, my_prio, their_ticket;
131
Andrew Thoelke958cc022014-06-09 12:54:15 +0100132 me = platform_get_core_pos(read_mpidr_el1());
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000133
134 assert_bakery_entry_valid(me, bakery);
135
136 /* Prevent recursive acquisition */
137 assert(bakery->owner != me);
138
139 /* Get a ticket */
140 my_ticket = bakery_get_ticket(bakery, me);
141
142 /*
143 * Now that we got our ticket, compute our priority value, then compare
144 * with that of others, and proceed to acquire the lock
145 */
146 my_prio = PRIORITY(my_ticket, me);
147 for (they = 0; they < BAKERY_LOCK_MAX_CPUS; they++) {
148 if (me == they)
149 continue;
150
151 /* Wait for the contender to get their ticket */
152 while (bakery->entering[they])
153 wfe();
154
155 /*
156 * If the other party is a contender, they'll have non-zero
157 * (valid) ticket value. If they do, compare priorities
158 */
159 their_ticket = bakery->number[they];
160 if (their_ticket && (PRIORITY(their_ticket, they) < my_prio)) {
161 /*
162 * They have higher priority (lower value). Wait for
163 * their ticket value to change (either release the lock
164 * to have it dropped to 0; or drop and probably content
165 * again for the same lock to have an even higher value)
166 */
167 do {
168 wfe();
169 } while (their_ticket == bakery->number[they]);
Achin Gupta4f6ad662013-10-25 09:08:21 +0100170 }
Achin Gupta4f6ad662013-10-25 09:08:21 +0100171 }
172
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000173 /* Lock acquired */
174 bakery->owner = me;
Achin Gupta4f6ad662013-10-25 09:08:21 +0100175}
176
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000177
178/* Release the lock and signal contenders */
Andrew Thoelke958cc022014-06-09 12:54:15 +0100179void bakery_lock_release(bakery_lock_t *bakery)
Achin Gupta4f6ad662013-10-25 09:08:21 +0100180{
Andrew Thoelke958cc022014-06-09 12:54:15 +0100181 unsigned int me = platform_get_core_pos(read_mpidr_el1());
Achin Gupta4f6ad662013-10-25 09:08:21 +0100182
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000183 assert_bakery_entry_valid(me, bakery);
184 assert(bakery->owner == me);
Achin Gupta4f6ad662013-10-25 09:08:21 +0100185
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000186 /*
187 * Release lock by resetting ownership and ticket. Then signal other
188 * waiting contenders
189 */
Achin Gupta4f6ad662013-10-25 09:08:21 +0100190 bakery->owner = NO_OWNER;
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000191 bakery->number[me] = 0;
192 sev();
Achin Gupta4f6ad662013-10-25 09:08:21 +0100193}