blob: 6bdc35a5eb5fa8682b79a5a205965968c0482514 [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;
Achin Gupta4f6ad662013-10-25 09:08:21 +0100110
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000111 return my_ticket;
112}
Achin Gupta4f6ad662013-10-25 09:08:21 +0100113
Achin Gupta4f6ad662013-10-25 09:08:21 +0100114
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000115/*
116 * Acquire bakery lock
117 *
118 * Contending CPUs need first obtain a non-zero ticket and then calculate
119 * priority value. A contending CPU iterate over all other CPUs in the platform,
120 * which may be contending for the same lock, in the order of their ordinal
121 * position (CPU0, CPU1 and so on). A non-contending CPU will have its ticket
122 * (and priority) value as 0. The contending CPU compares its priority with that
123 * of others'. The CPU with the highest priority (lowest numerical value)
124 * acquires the lock
125 */
Andrew Thoelke958cc022014-06-09 12:54:15 +0100126void bakery_lock_get(bakery_lock_t *bakery)
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000127{
128 unsigned int they, me;
129 unsigned int my_ticket, my_prio, their_ticket;
130
Andrew Thoelke958cc022014-06-09 12:54:15 +0100131 me = platform_get_core_pos(read_mpidr_el1());
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000132
133 assert_bakery_entry_valid(me, bakery);
134
135 /* Prevent recursive acquisition */
136 assert(bakery->owner != me);
137
138 /* Get a ticket */
139 my_ticket = bakery_get_ticket(bakery, me);
140
141 /*
142 * Now that we got our ticket, compute our priority value, then compare
143 * with that of others, and proceed to acquire the lock
144 */
145 my_prio = PRIORITY(my_ticket, me);
146 for (they = 0; they < BAKERY_LOCK_MAX_CPUS; they++) {
147 if (me == they)
148 continue;
149
150 /* Wait for the contender to get their ticket */
151 while (bakery->entering[they])
Soby Mathew6b98c7d2014-11-18 10:45:04 +0000152 ;
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000153
154 /*
155 * If the other party is a contender, they'll have non-zero
156 * (valid) ticket value. If they do, compare priorities
157 */
158 their_ticket = bakery->number[they];
159 if (their_ticket && (PRIORITY(their_ticket, they) < my_prio)) {
160 /*
161 * They have higher priority (lower value). Wait for
162 * their ticket value to change (either release the lock
163 * to have it dropped to 0; or drop and probably content
164 * again for the same lock to have an even higher value)
165 */
166 do {
167 wfe();
168 } while (their_ticket == bakery->number[they]);
Achin Gupta4f6ad662013-10-25 09:08:21 +0100169 }
Achin Gupta4f6ad662013-10-25 09:08:21 +0100170 }
171
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000172 /* Lock acquired */
173 bakery->owner = me;
Achin Gupta4f6ad662013-10-25 09:08:21 +0100174}
175
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000176
177/* Release the lock and signal contenders */
Andrew Thoelke958cc022014-06-09 12:54:15 +0100178void bakery_lock_release(bakery_lock_t *bakery)
Achin Gupta4f6ad662013-10-25 09:08:21 +0100179{
Andrew Thoelke958cc022014-06-09 12:54:15 +0100180 unsigned int me = platform_get_core_pos(read_mpidr_el1());
Achin Gupta4f6ad662013-10-25 09:08:21 +0100181
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000182 assert_bakery_entry_valid(me, bakery);
183 assert(bakery->owner == me);
Achin Gupta4f6ad662013-10-25 09:08:21 +0100184
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000185 /*
186 * Release lock by resetting ownership and ticket. Then signal other
187 * waiting contenders
188 */
Achin Gupta4f6ad662013-10-25 09:08:21 +0100189 bakery->owner = NO_OWNER;
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000190 bakery->number[me] = 0;
Achin Guptaed04c4a2014-11-10 11:50:30 +0000191 dsb();
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000192 sev();
Achin Gupta4f6ad662013-10-25 09:08:21 +0100193}