blob: 5d538ce2c6afc301ed9d0ec6f92c2121f0ced92d [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>
Soby Mathew523d6332015-01-08 18:02:19 +000034#include <cpu_data.h>
Dan Handleyed6ff952014-05-14 17:44:19 +010035#include <platform.h>
Dan Handley2bd4ef22014-04-09 13:14:54 +010036#include <string.h>
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +000037
38/*
Soby Mathew523d6332015-01-08 18:02:19 +000039 * Functions in this file implement Bakery Algorithm for mutual exclusion with the
40 * bakery lock data structures in coherent memory.
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +000041 *
42 * ARM architecture offers a family of exclusive access instructions to
43 * efficiently implement mutual exclusion with hardware support. However, as
44 * well as depending on external hardware, the these instructions have defined
45 * behavior only on certain memory types (cacheable and Normal memory in
46 * particular; see ARMv8 Architecture Reference Manual section B2.10). Use cases
47 * in trusted firmware are such that mutual exclusion implementation cannot
48 * expect that accesses to the lock have the specific type required by the
49 * architecture for these primitives to function (for example, not all
50 * contenders may have address translation enabled).
51 *
52 * This implementation does not use mutual exclusion primitives. It expects
53 * memory regions where the locks reside to be fully ordered and coherent
54 * (either by disabling address translation, or by assigning proper attributes
55 * when translation is enabled).
56 *
57 * Note that the ARM architecture guarantees single-copy atomicity for aligned
58 * accesses regardless of status of address translation.
59 */
Achin Gupta4f6ad662013-10-25 09:08:21 +010060
61#define assert_bakery_entry_valid(entry, bakery) do { \
62 assert(bakery); \
63 assert(entry < BAKERY_LOCK_MAX_CPUS); \
Dan Handleya70615f2014-04-09 12:48:25 +010064} while (0)
Achin Gupta4f6ad662013-10-25 09:08:21 +010065
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +000066/* Convert a ticket to priority */
67#define PRIORITY(t, pos) (((t) << 8) | (pos))
68
69
70/* Initialize Bakery Lock to reset ownership and all ticket values */
Dan Handleye2712bc2014-04-10 15:37:22 +010071void bakery_lock_init(bakery_lock_t *bakery)
Achin Gupta4f6ad662013-10-25 09:08:21 +010072{
73 assert(bakery);
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +000074
75 /* All ticket values need to be 0 */
Achin Gupta4f6ad662013-10-25 09:08:21 +010076 memset(bakery, 0, sizeof(*bakery));
77 bakery->owner = NO_OWNER;
78}
79
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +000080
81/* Obtain a ticket for a given CPU */
Dan Handleye2712bc2014-04-10 15:37:22 +010082static unsigned int bakery_get_ticket(bakery_lock_t *bakery, unsigned int me)
Achin Gupta4f6ad662013-10-25 09:08:21 +010083{
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +000084 unsigned int my_ticket, their_ticket;
85 unsigned int they;
Achin Gupta4f6ad662013-10-25 09:08:21 +010086
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +000087 /*
88 * Flag that we're busy getting our ticket. All CPUs are iterated in the
89 * order of their ordinal position to decide the maximum ticket value
90 * observed so far. Our priority is set to be greater than the maximum
91 * observed priority
92 *
93 * Note that it's possible that more than one contender gets the same
94 * ticket value. That's OK as the lock is acquired based on the priority
95 * value, not the ticket value alone.
96 */
97 my_ticket = 0;
98 bakery->entering[me] = 1;
99 for (they = 0; they < BAKERY_LOCK_MAX_CPUS; they++) {
100 their_ticket = bakery->number[they];
101 if (their_ticket > my_ticket)
102 my_ticket = their_ticket;
103 }
Achin Gupta4f6ad662013-10-25 09:08:21 +0100104
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000105 /*
106 * Compute ticket; then signal to other contenders waiting for us to
107 * finish calculating our ticket value that we're done
108 */
109 ++my_ticket;
110 bakery->number[me] = my_ticket;
111 bakery->entering[me] = 0;
Achin Gupta4f6ad662013-10-25 09:08:21 +0100112
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000113 return my_ticket;
114}
Achin Gupta4f6ad662013-10-25 09:08:21 +0100115
Achin Gupta4f6ad662013-10-25 09:08:21 +0100116
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000117/*
118 * Acquire bakery lock
119 *
120 * Contending CPUs need first obtain a non-zero ticket and then calculate
121 * priority value. A contending CPU iterate over all other CPUs in the platform,
122 * which may be contending for the same lock, in the order of their ordinal
123 * position (CPU0, CPU1 and so on). A non-contending CPU will have its ticket
124 * (and priority) value as 0. The contending CPU compares its priority with that
125 * of others'. The CPU with the highest priority (lowest numerical value)
126 * acquires the lock
127 */
Andrew Thoelke958cc022014-06-09 12:54:15 +0100128void bakery_lock_get(bakery_lock_t *bakery)
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000129{
130 unsigned int they, me;
131 unsigned int my_ticket, my_prio, their_ticket;
132
Andrew Thoelke958cc022014-06-09 12:54:15 +0100133 me = platform_get_core_pos(read_mpidr_el1());
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000134
135 assert_bakery_entry_valid(me, bakery);
136
137 /* Prevent recursive acquisition */
138 assert(bakery->owner != me);
139
140 /* Get a ticket */
141 my_ticket = bakery_get_ticket(bakery, me);
142
143 /*
144 * Now that we got our ticket, compute our priority value, then compare
145 * with that of others, and proceed to acquire the lock
146 */
147 my_prio = PRIORITY(my_ticket, me);
148 for (they = 0; they < BAKERY_LOCK_MAX_CPUS; they++) {
149 if (me == they)
150 continue;
151
152 /* Wait for the contender to get their ticket */
153 while (bakery->entering[they])
Soby Mathew6b98c7d2014-11-18 10:45:04 +0000154 ;
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000155
156 /*
157 * If the other party is a contender, they'll have non-zero
158 * (valid) ticket value. If they do, compare priorities
159 */
160 their_ticket = bakery->number[they];
161 if (their_ticket && (PRIORITY(their_ticket, they) < my_prio)) {
162 /*
163 * They have higher priority (lower value). Wait for
164 * their ticket value to change (either release the lock
165 * to have it dropped to 0; or drop and probably content
166 * again for the same lock to have an even higher value)
167 */
168 do {
169 wfe();
170 } while (their_ticket == bakery->number[they]);
Achin Gupta4f6ad662013-10-25 09:08:21 +0100171 }
Achin Gupta4f6ad662013-10-25 09:08:21 +0100172 }
173
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000174 /* Lock acquired */
175 bakery->owner = me;
Achin Gupta4f6ad662013-10-25 09:08:21 +0100176}
177
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000178
179/* Release the lock and signal contenders */
Andrew Thoelke958cc022014-06-09 12:54:15 +0100180void bakery_lock_release(bakery_lock_t *bakery)
Achin Gupta4f6ad662013-10-25 09:08:21 +0100181{
Andrew Thoelke958cc022014-06-09 12:54:15 +0100182 unsigned int me = platform_get_core_pos(read_mpidr_el1());
Achin Gupta4f6ad662013-10-25 09:08:21 +0100183
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000184 assert_bakery_entry_valid(me, bakery);
185 assert(bakery->owner == me);
Achin Gupta4f6ad662013-10-25 09:08:21 +0100186
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000187 /*
188 * Release lock by resetting ownership and ticket. Then signal other
189 * waiting contenders
190 */
Achin Gupta4f6ad662013-10-25 09:08:21 +0100191 bakery->owner = NO_OWNER;
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000192 bakery->number[me] = 0;
Achin Guptaed04c4a2014-11-10 11:50:30 +0000193 dsb();
Jeenu Viswambharanbe87cfc2014-03-13 11:16:25 +0000194 sev();
Achin Gupta4f6ad662013-10-25 09:08:21 +0100195}