1 /*
2 * This file and its contents are supplied under the terms of the
3 * Common Development and Distribution License ("CDDL"), version 1.0.
4 * You may only use this file in accordance with the terms of version
5 * 1.0 of the CDDL.
6 *
7 * A full copy of the text of the CDDL should have accompanied this
8 * source. A copy of the CDDL is also available via the Internet at
9 * http://www.illumos.org/license/CDDL.
10 */
11
12 /*
13 * Copyright 2025 Oxide Computer Company
14 */
15
16 /*
17 * This file contains all of the logic around how we look for overlapping
18 * addresses. Addresses must uniquely identify a device on a given bus. The
19 * logic in this file currently assumes each address type (e.g. 7-bit vs.
20 * 10-bit) is a unique and non-overlapping space. That is the 7-bit and 10-bit
21 * address 0x23 is different and cannot find one another. As with most things in
22 * I2C this would be simple were it not for the case of multiplexers.
23 *
24 * As the kernel only allows a single segment on a mux to be active at any given
25 * time, addresses below a mux are allowed to be duplicated as both cannot be
26 * addressed. However addresses on different segments gets tricky fast. Consider
27 * the following different bus topologies:
28 *
29 * -------------
30 * Flat Topology
31 * -------------
32 *
33 * All devices are connected to the controller with no intermediate bus.
34 *
35 * +------------+
36 * | Controller |
37 * +------------+
38 * |
39 * v
40 * A
41 *
42 * This is the simplest case. Basically we can use each non-reserved address
43 * once in A and tracking this is relatively easy.
44 *
45 * ----------
46 * Single Mux
47 * ----------
48 *
49 * There is a single mux in the tree with multiple segments under it. This looks
50 * like:
51 *
52 * +------------+
53 * | Controller |
54 * +------------+
55 * |
56 * |-- A
57 * v
58 * +------------+
59 * | Mux |
60 * | |
61 * | 0 1 2 3 |
62 * +------------+
63 * | | | |
64 * v v v v
65 * B C D E
66 *
67 * In this case we would allow address overlap between the downstream segments
68 * of the mux. However, if an address is used in portion A, it cannot be used in
69 * B-E. Similarly, if something is used in B-E, it can't really be used in A as
70 * there would be now way to actually access it.
71 *
72 * ------------------
73 * Single Layer Muxes
74 * ------------------
75 *
76 * This is a variant on the previous case where we have multiple muxes, that
77 * exist in parallel to one another. This often happens where someone is using
78 * multiple 4-port muxes to deal with overlap. Let's draw this out and see how
79 * our rules change:
80 *
81 * +------------+
82 * | Controller |
83 * +------------+
84 * |
85 * |-- A
86 * +----------+---------+
87 * v v
88 * +------------+ +------------+
89 * | Mux | | Mux |
90 * | | | |
91 * | 0 1 2 3 | | 0 1 2 3 |
92 * +------------+ +------------+
93 * | | | | | | | |
94 * v v v v v v v v
95 * B C D E F G H I
96 *
97 * In this case our rules are actually the same as in the prior case. While the
98 * two muxes may be different devices, we basically say that anything in B-I can
99 * overlap. However, the fact that we can't have an address both A and in B-I
100 * still remains. This leads to a rule: muxes at the same level of the tree
101 * should be considered the same.
102 *
103 * ---------------
104 * Two Layer Muxes
105 * ---------------
106 *
107 * Let's go back to the Single mux case and say no what happens if say C above
108 * had a mux under it. First, let's draw this out:
109 *
110 * +------------+
111 * | Controller |
112 * +------------+
113 * |
114 * |-- A
115 * v
116 * +------------+
117 * | Mux |
118 * | |
119 * | 0 1 2 3 |
120 * +------------+
121 * | | | |
122 * v | v v
123 * B | D E
124 * |
125 * |-- C
126 * v
127 * +------------+
128 * | Mux |
129 * | |
130 * | 0 1 2 3 |
131 * +------------+
132 * | | | |
133 * v v v v
134 * F G H I
135 *
136 * So this design is not uncommon. Let's start with the simplest statement
137 * possible: F-I can use overlapping addresses. The next one is more fun.
138 * Anything in F-I can overlap in B, D, and E. Why is that? Basically this is
139 * the same as the single layer mux. Similarly, anything in A cannot be used
140 * elsewhere nor can something be added to A that is used elsewhere.
141 *
142 * Now some wrinkles: Anything in C can still be used in B, D, and E, but it
143 * cannot be used in F-I. This mostly makes sense as it follows the single mux
144 * case.
145 *
146 * ----------
147 * Mux Forest
148 * ----------
149 *
150 * Let's look at a complex series of muxes.
151 * *
152 * +------------+
153 * | Controller |
154 * +------------+
155 * |
156 * |-- A
157 * +----------+---------+
158 * v v
159 * +------------+ +------------+
160 * | Mux | | Mux |
161 * | | | |
162 * | 0 1 2 3 | | 0 1 2 3 |
163 * +------------+ +------------+
164 * | | | | | | | |
165 * v | v v v v | v
166 * B | D E F G | I
167 * | |
168 * |-- C |-- H
169 * +--------+-------+ v
170 * v v +------------+
171 * +------------+ +------------+ | Mux |
172 * | Mux | | Mux | | |
173 * | | | | | 0 1 2 3 |
174 * | 0 1 2 3 | | 0 1 2 3 | +------------+
175 * +------------+ +------------+ | | | |
176 * | | | | | | | | v v v v
177 * v v v v v v v v R S T U
178 * J K L M N O P Q
179 *
180 * So we have a lot more going on here. Let's take this apart a bit. Let's start
181 * with the first layer. This is covered by the Single Layer Mux rules. So what
182 * happens when we start looking at their next layers. Let's start with the
183 * right hand side and lay out a few observations:
184 *
185 * - Addresses in R-U can overlap as much as they'd like per the normal single
186 * mux rule.
187 * - Addresses in R-U and H cannot overlap per the normal single mux rule.
188 * - Going up, Address in F, G, H, I are allowed to overlap. Similarly any
189 * addresses in R-U can be thought of as part of H while evaluating at this
190 * layer.
191 * - The implications of the above are that addresses in F, G, and I can
192 * overlap with any addresses in R-U.
193 * - Similarly, any address used in F-I and R-U cannot be used in A.
194 *
195 * Let's now pause and shift over to the left hand side of this forest before.
196 * Similar to the single layer mux rules we can say the following:
197 *
198 * - J-Q are allowed to overlap as much as they'd like.
199 * - C cannot overlap with J-Q.
200 * - B, D, and E can overlap with C and J-Q as much as they'd like.
201 * - All of these cannot overlap at all with A.
202 *
203 * -------------
204 * Rules Summary
205 * -------------
206 *
207 * 1) Muxes at the same level in the hierarchy can be thought of as one giant
208 * mux.
209 * 2) Address overlap is always allowed for all the ports in the giant mux
210 * description from (1). Treat the set of used addresses on a giant mux as
211 * the union of all addresses used on all ports downstream.
212 * 3) The union of addresses described in (2) cannot overlap with any upstream
213 * segments. For example:
214 * - The union of R-U cannot overlap with H.
215 * - The union of J-Q cannot overlap with C.
216 * - The union of B-U cannot overlap with A.
217 * 4) These same sets of rules apply recursively throughout the tree.
218 *
219 * This means that when adding an address at any point in the three, it is
220 * subject to the design of the rest of the tree. Note, it is strictly possible
221 * to create something which is not actually a tree electrically. We don't
222 * really have a good way of representing that and it definitely fits into the
223 * I2C muxes are cursed territory. If we decided to support that, then we'll
224 * have to revisit this and the set of rules.
225 *
226 * ------------------------------
227 * Device with Multiple Addresses
228 * ------------------------------
229 *
230 * There are two groups of devices with multiple addresses:
231 *
232 * 1) Those that have exclusive access to multiple addresses.
233 * 2) Those that have an exclusive address and share a common address on the
234 * bus across all instances. The most prevalent example is the DDR4 EEPROM.
235 * All DDR4 EEPROMs share the same address to change a page.
236 *
237 * Issuing addresses in group (1) follows the same process as we have done to
238 * date. However, we need a useful way to deal with group (2). To help this out
239 * we make the following assumptions:
240 *
241 * 1) Only a single driver (e.g. a major_t) will need access to this at a time.
242 * A driver that uses this interface will know it is requesting it and can
243 * know how to coordinate usage of this address and the implications it has
244 * on devices.
245 * 2) This will not be specified in reg[] information for the time being. This
246 * ensures that we always have a known driver and therefore a major_t to
247 * facilitate this.
248 *
249 * To facilitate this, we augment our tracking data with the major_t. We use
250 * DDI_MAJOR_T_NONE to indicate that this is an exclusive address and the actual
251 * major_t of the driver that owns it to indicate both that it is shared and
252 * with whom.
253 *
254 * --------------
255 * Implementation
256 * --------------
257 *
258 * We are generally concerned with the address use from any series of i2c_port_t
259 * instances in the tree. Basically a port is something that can have some
260 * number of devices under it, whether it is a port on a controller, downstream
261 * ports of an analog switch, or an in-band or out-of-band multiplexor, or
262 * something else.
263 *
264 * A given port tracks all of the addresses that are in use immediately under it
265 * and of all subsequent ports under it. For each address that is usable we
266 * include a reference count, whether it is from our segment or a downstream
267 * segment, and a major_t that is used to indicate whether this is a shared
268 * address or not. This then occurs recursively up the tree. A few notes on how
269 * this is used:
270 *
271 * 1) To determine if something is in use or not, you have to consult your port
272 * and all of the parent ports. However, you do not have to iterate over all
273 * ports in the tree.
274 *
275 * 2) The top-level port, aka the bus, tells us all addresses that are in use.
276 * However, it doesn't not immediately answer the question of whether or not an
277 * address can be used.
278 *
279 * 3) Exclusive addresses mark their way all the way up the tree; however,
280 * shared addresses only consult the bus.
281 *
282 * 3) The overall algorithm for determining if an address is usable or not for
283 * exclusive access is:
284 *
285 * if current port reference count is non-zero:
286 * return false
287 * for each parent:
288 * if the reference count is zero:
289 * continue
290 * if the reference count is the maximum value:
291 * return false
292 * if the address is in use directly or it has a
293 * non-DDI_MAJOR_T_NONE major:
294 * return false
295 * return true
296 *
297 * 4) To actually indicate that the address is in use you set the reference
298 * count to 1 on the current port, mark it as directly used, and store the major
299 * as DDI_MAJOR_T_NONE. Then for each case up the tree you bump the reference
300 * count, validate it as remote, and that it has DDI_MAJOR_T_NONE as the major.
301 *
302 * 5) When removing an address, you decrement the reference count for this
303 * address on each port up the tree.
304 *
305 * 6) The overall algorithm for determining if an address is usable or not for a
306 * shared address is:
307 *
308 * got to the bus
309 * if the reference count is non-zero:
310 * if the stored major differs from the caller's:
311 * return false
312 * if the reference count is the maximum value:
313 * return false
314 * return true
315 *
316 * Because all exclusive addresses always go all the way up the tree to the bus,
317 * we can easily use this and simplify the implementation and don't have to walk
318 * everywhere to determine conflicts on mux segments.
319 *
320 * 6) To indicate that a shared reference address is in use one goes to the bus.
321 * Bump the reference count by one and ensure the major is set as expected and
322 * that this is set as direct.
323 *
324 * 7) When removing an address, you decrement the reference count on the
325 * top-most bus port. If the reference count is now zero, reset the major and
326 * direct bit.
327 *
328 * 8) The major and direct bits are only valid if the reference-count is
329 * non-zero.
330 *
331 * The above information is tracked on a per-address family basis. The reference
332 * count is currently constrained to a uint8_t. This can be increased if the
333 * need is there.
334 */
335
336 #include "i2cnex.h"
337
338 static bool
i2c_addr_free_parent(i2c_port_t * port,void * arg)339 i2c_addr_free_parent(i2c_port_t *port, void *arg)
340 {
341 const i2c_addr_t *addr = arg;
342 i2c_addr_track_t *track = &port->ip_track_7b;
343 VERIFY3U(addr->ia_type, ==, I2C_ADDR_7BIT);
344 VERIFY3U(track->at_refcnt[addr->ia_addr], >, 0);
345 VERIFY3U(track->at_downstream[addr->ia_addr], ==, true);
346 VERIFY3U(track->at_major[addr->ia_addr], ==, DDI_MAJOR_T_NONE);
347
348 track->at_refcnt[addr->ia_addr]--;
349 if (track->at_refcnt[addr->ia_addr] == 0) {
350 track->at_downstream[addr->ia_addr] = false;
351 track->at_major[addr->ia_addr] = DDI_MAJOR_T_UNKNOWN;
352 }
353
354 return (true);
355 }
356
357 void
i2c_addr_free(i2c_port_t * port,const i2c_addr_t * addr)358 i2c_addr_free(i2c_port_t *port, const i2c_addr_t *addr)
359 {
360 i2c_addr_track_t *track;
361
362 VERIFY3P(port->ip_nex->in_ctrl->ic_lock.cl_owner, !=, NULL);
363 VERIFY3U(addr->ia_type, ==, I2C_ADDR_7BIT);
364
365 track = &port->ip_track_7b;
366 VERIFY3U(track->at_refcnt[addr->ia_addr], >, 0);
367 VERIFY3U(track->at_major[addr->ia_addr], ==, DDI_MAJOR_T_NONE);
368 VERIFY3U(track->at_downstream[addr->ia_addr], ==, false);
369 track->at_refcnt[addr->ia_addr]--;
370 if (track->at_refcnt[addr->ia_addr] == 0) {
371 track->at_downstream[addr->ia_addr] = false;
372 track->at_major[addr->ia_addr] = DDI_MAJOR_T_UNKNOWN;
373 }
374
375 i2c_port_parent_iter(port, i2c_addr_free_parent, (void *)addr);
376 }
377
378 typedef struct {
379 const i2c_addr_t *ipa_addr;
380 i2c_error_t *ipa_err;
381 bool ipa_valid;
382 } i2c_addr_check_t;
383
384 static bool
i2c_addr_alloc_check(i2c_port_t * port,void * arg)385 i2c_addr_alloc_check(i2c_port_t *port, void *arg)
386 {
387 i2c_addr_check_t *check = arg;
388 i2c_addr_track_t *track = &port->ip_track_7b;
389 uint16_t idx = check->ipa_addr->ia_addr;
390
391 VERIFY3U(check->ipa_addr->ia_type, ==, I2C_ADDR_7BIT);
392
393 if (track->at_refcnt[idx] == 0) {
394 return (true);
395 }
396
397 if (track->at_refcnt[idx] == UINT8_MAX) {
398 check->ipa_valid = false;
399 return (i2c_error(check->ipa_err, I2C_CORE_E_ADDR_REFCNT, 0));
400 }
401
402 /*
403 * While we store DDI_MAJOR_T_UNKNOWN (0) in the case where the
404 * reference count is zero, we have already dealt with that up above.
405 */
406 if (!track->at_downstream[idx] ||
407 track->at_major[idx] != DDI_MAJOR_T_NONE) {
408 check->ipa_valid = false;
409 return (i2c_error(check->ipa_err, I2C_CORE_E_ADDR_IN_USE, 0));
410 }
411
412 return (true);
413 }
414
415 static bool
i2c_addr_alloc_parent(i2c_port_t * port,void * arg)416 i2c_addr_alloc_parent(i2c_port_t *port, void *arg)
417 {
418 const i2c_addr_t *addr = arg;
419 i2c_addr_track_t *track = &port->ip_track_7b;
420
421 VERIFY3P(port->ip_nex->in_ctrl->ic_lock.cl_owner, !=, NULL);
422 VERIFY3U(addr->ia_type, ==, I2C_ADDR_7BIT);
423
424 if (track->at_refcnt[addr->ia_addr] > 0) {
425 VERIFY3U(track->at_downstream[addr->ia_addr], ==, true);
426 VERIFY3U(track->at_major[addr->ia_addr], ==, DDI_MAJOR_T_NONE);
427 } else {
428 track->at_downstream[addr->ia_addr] = true;
429 track->at_major[addr->ia_addr] = DDI_MAJOR_T_NONE;
430 }
431
432 track->at_refcnt[addr->ia_addr]++;
433 return (true);
434 }
435
436 bool
i2c_addr_alloc(i2c_port_t * port,const i2c_addr_t * addr,i2c_error_t * err)437 i2c_addr_alloc(i2c_port_t *port, const i2c_addr_t *addr, i2c_error_t *err)
438 {
439 i2c_addr_track_t *track;
440 i2c_addr_check_t check;
441
442 VERIFY3P(port->ip_nex->in_ctrl->ic_lock.cl_owner, !=, NULL);
443 VERIFY3U(addr->ia_type, ==, I2C_ADDR_7BIT);
444
445 track = &port->ip_track_7b;
446 if (track->at_refcnt[addr->ia_addr] != 0) {
447 return (i2c_error(err, I2C_CORE_E_ADDR_IN_USE, 0));
448 }
449
450 check.ipa_addr = addr;
451 check.ipa_err = err;
452 check.ipa_valid = true;
453 i2c_port_parent_iter(port, i2c_addr_alloc_check, &check);
454 if (!check.ipa_valid) {
455 return (false);
456 }
457
458 track->at_refcnt[addr->ia_addr]++;
459 track->at_downstream[addr->ia_addr] = false;
460 track->at_major[addr->ia_addr] = DDI_MAJOR_T_NONE;
461 i2c_port_parent_iter(port, i2c_addr_alloc_parent, (void *)addr);
462 return (true);
463 }
464
465 static i2c_port_t *
i2c_port_topmost(i2c_port_t * port)466 i2c_port_topmost(i2c_port_t *port)
467 {
468 i2c_port_t *last = port;
469
470 VERIFY3P(port->ip_nex->in_ctrl->ic_lock.cl_owner, !=, NULL);
471
472 for (i2c_nexus_t *nex = port->ip_nex->in_pnex; nex != NULL;
473 nex = nex->in_pnex) {
474 if (nex->in_type == I2C_NEXUS_T_PORT) {
475 last = nex->in_data.in_port;
476 }
477 }
478
479 return (last);
480 }
481
482 typedef struct {
483 const i2c_addr_t *iaa_addr;
484 major_t iaa_major;
485 } i2c_addr_alloc_t;
486
487 static bool
i2c_addr_free_shared_cb(i2c_port_t * port,void * arg)488 i2c_addr_free_shared_cb(i2c_port_t *port, void *arg)
489 {
490 const i2c_addr_alloc_t *alloc = arg;
491 const i2c_addr_t *addr = alloc->iaa_addr;
492 i2c_addr_track_t *track;
493
494 VERIFY3P(port->ip_nex->in_ctrl->ic_lock.cl_owner, !=, NULL);
495 VERIFY3U(addr->ia_type, ==, I2C_ADDR_7BIT);
496
497 track = &port->ip_track_7b;
498 VERIFY3U(track->at_refcnt[addr->ia_addr], >, 0);
499 VERIFY3U(track->at_downstream[addr->ia_addr], ==, false);
500 VERIFY3U(track->at_major[addr->ia_addr], ==, alloc->iaa_major);
501
502 track->at_refcnt[addr->ia_addr]--;
503 if (track->at_refcnt[addr->ia_addr] == 0) {
504 track->at_downstream[addr->ia_addr] = false;
505 track->at_major[addr->ia_addr] = DDI_MAJOR_T_UNKNOWN;
506 }
507
508 return (true);
509 }
510
511 void
i2c_addr_free_shared(i2c_port_t * port,const i2c_addr_t * addr,major_t maj)512 i2c_addr_free_shared(i2c_port_t *port, const i2c_addr_t *addr, major_t maj)
513 {
514 i2c_addr_alloc_t alloc;
515
516 VERIFY3P(port->ip_nex->in_ctrl->ic_lock.cl_owner, !=, NULL);
517 VERIFY3U(addr->ia_type, ==, I2C_ADDR_7BIT);
518 alloc.iaa_addr = addr;
519 alloc.iaa_major = maj;
520 (void) i2c_port_iter(port, i2c_addr_free_shared_cb, &alloc);
521 }
522
523 static bool
i2c_addr_alloc_shared_cb(i2c_port_t * port,void * arg)524 i2c_addr_alloc_shared_cb(i2c_port_t *port, void *arg)
525 {
526 const i2c_addr_alloc_t *alloc = arg;
527 const i2c_addr_t *addr = alloc->iaa_addr;
528 i2c_addr_track_t *track = &port->ip_track_7b;
529
530 VERIFY3P(port->ip_nex->in_ctrl->ic_lock.cl_owner, !=, NULL);
531 VERIFY3U(addr->ia_type, ==, I2C_ADDR_7BIT);
532
533 if (track->at_refcnt[addr->ia_addr] > 0) {
534 VERIFY3U(track->at_downstream[addr->ia_addr], ==, false);
535 VERIFY3U(track->at_major[addr->ia_addr], ==, alloc->iaa_major);
536 } else {
537 track->at_downstream[addr->ia_addr] = false;
538 track->at_major[addr->ia_addr] = alloc->iaa_major;
539 }
540
541 track->at_refcnt[addr->ia_addr]++;
542 return (true);
543 }
544
545 bool
i2c_addr_alloc_shared(i2c_port_t * port,const i2c_addr_t * addr,major_t maj,i2c_error_t * err)546 i2c_addr_alloc_shared(i2c_port_t *port, const i2c_addr_t *addr, major_t maj,
547 i2c_error_t *err)
548 {
549 i2c_port_t *bus;
550 i2c_addr_track_t *track;
551 i2c_addr_alloc_t alloc;
552
553 VERIFY3P(port->ip_nex->in_ctrl->ic_lock.cl_owner, !=, NULL);
554 VERIFY3U(addr->ia_type, ==, I2C_ADDR_7BIT);
555
556 /*
557 * For an address to be allocated as a shared address it must not be in
558 * use at the top-most port or be specifically a shared address there
559 * with our major. We never will set downstream for a shared address
560 * because it's complicated to track in this case and not relevant for
561 * shared addresses.
562 */
563 bus = i2c_port_topmost(port);
564 track = &bus->ip_track_7b;
565 if (track->at_refcnt[addr->ia_addr] != 0) {
566 if (track->at_major[addr->ia_addr] != maj) {
567 return (i2c_error(err, I2C_CORE_E_ADDR_IN_USE, 0));
568 }
569
570 if (track->at_refcnt[addr->ia_addr] == UINT8_MAX) {
571 return (i2c_error(err, I2C_CORE_E_ADDR_REFCNT, 0));
572 }
573
574 VERIFY3U(track->at_downstream[addr->ia_addr], ==, false);
575 }
576
577 alloc.iaa_addr = addr;
578 alloc.iaa_major = maj;
579 i2c_port_iter(port, i2c_addr_alloc_shared_cb, &alloc);
580
581 return (true);
582 }
583
584 void
i2c_addr_info_7b(const i2c_port_t * port,ui2c_port_info_t * info)585 i2c_addr_info_7b(const i2c_port_t *port, ui2c_port_info_t *info)
586 {
587 const i2c_addr_track_t *track = &port->ip_track_7b;
588
589 for (uint8_t i = 0; i < 1 << 7; i++) {
590 if (track->at_refcnt[i] == 0) {
591 info->upo_7b[i].pai_major = DDI_MAJOR_T_NONE;
592 info->upo_7b[i].pai_ndevs = 0;
593 info->upo_7b[i].pai_downstream = false;
594 continue;
595 }
596
597 info->upo_7b[i].pai_ndevs = track->at_refcnt[i];
598 info->upo_7b[i].pai_downstream = track->at_downstream[i];
599 info->upo_7b[i].pai_major = track->at_major[i];
600 }
601 }
602