forked from ~ljy/RK356X_SDK_RELEASE

blame | history | patch | commit | commitdiff
hc
2024-10-22 8ac6c7a54ed1b98d142dce24b11c6de6a1e239a5 
 kernel/net/tipc/name_table.c
....@@ -35,6 +35,8 @@
3535  */
3636 
3737 #include <net/sock.h>
38
+#include <linux/list_sort.h>
39
+#include <linux/rbtree_augmented.h>
3840 #include "core.h"
3941 #include "netlink.h"
4042 #include "name_table.h"
....@@ -50,6 +52,7 @@
5052  * @lower: service range lower bound
5153  * @upper: service range upper bound
5254  * @tree_node: member of service range RB tree
55
+ * @max: largest 'upper' in this node subtree
5356  * @local_publ: list of identical publications made from this node
5457  *   Used by closest_first lookup and multicast lookup algorithm
5558  * @all_publ: all publications identical to this one, whatever node and scope
....@@ -59,6 +62,7 @@
5962 	u32 lower;
6063 	u32 upper;
6164 	struct rb_node tree_node;
65
+	u32 max;
6266 	struct list_head local_publ;
6367 	struct list_head all_publ;
6468 };
....@@ -66,6 +70,7 @@
6670 /**
6771  * struct tipc_service - container for all published instances of a service type
6872  * @type: 32 bit 'type' value for service
73
+ * @publ_cnt: increasing counter for publications in this service
6974  * @ranges: rb tree containing all service ranges for this service
7075  * @service_list: links to adjacent name ranges in hash chain
7176  * @subscriptions: list of subscriptions for this service type
....@@ -74,12 +79,137 @@
7479  */
7580 struct tipc_service {
7681 	u32 type;
82
+	u32 publ_cnt;
7783 	struct rb_root ranges;
7884 	struct hlist_node service_list;
7985 	struct list_head subscriptions;
8086 	spinlock_t lock; /* Covers service range list */
8187 	struct rcu_head rcu;
8288 };
89
+
90
+#define service_range_upper(sr) ((sr)->upper)
91
+RB_DECLARE_CALLBACKS_MAX(static, sr_callbacks,
92
+			 struct service_range, tree_node, u32, max,
93
+			 service_range_upper)
94
+
95
+#define service_range_entry(rbtree_node)				\
96
+	(container_of(rbtree_node, struct service_range, tree_node))
97
+
98
+#define service_range_overlap(sr, start, end)				\
99
+	((sr)->lower <= (end) && (sr)->upper >= (start))
100
+
101
+/**
102
+ * service_range_foreach_match - iterate over tipc service rbtree for each
103
+ *                               range match
104
+ * @sr: the service range pointer as a loop cursor
105
+ * @sc: the pointer to tipc service which holds the service range rbtree
106
+ * @start, end: the range (end >= start) for matching
107
+ */
108
+#define service_range_foreach_match(sr, sc, start, end)			\
109
+	for (sr = service_range_match_first((sc)->ranges.rb_node,	\
110
+					    start,			\
111
+					    end);			\
112
+	     sr;							\
113
+	     sr = service_range_match_next(&(sr)->tree_node,		\
114
+					   start,			\
115
+					   end))
116
+
117
+/**
118
+ * service_range_match_first - find first service range matching a range
119
+ * @n: the root node of service range rbtree for searching
120
+ * @start, end: the range (end >= start) for matching
121
+ *
122
+ * Return: the leftmost service range node in the rbtree that overlaps the
123
+ * specific range if any. Otherwise, returns NULL.
124
+ */
125
+static struct service_range *service_range_match_first(struct rb_node *n,
126
+						       u32 start, u32 end)
127
+{
128
+	struct service_range *sr;
129
+	struct rb_node *l, *r;
130
+
131
+	/* Non overlaps in tree at all? */
132
+	if (!n || service_range_entry(n)->max < start)
133
+		return NULL;
134
+
135
+	while (n) {
136
+		l = n->rb_left;
137
+		if (l && service_range_entry(l)->max >= start) {
138
+			/* A leftmost overlap range node must be one in the left
139
+			 * subtree. If not, it has lower > end, then nodes on
140
+			 * the right side cannot satisfy the condition either.
141
+			 */
142
+			n = l;
143
+			continue;
144
+		}
145
+
146
+		/* No one in the left subtree can match, return if this node is
147
+		 * an overlap i.e. leftmost.
148
+		 */
149
+		sr = service_range_entry(n);
150
+		if (service_range_overlap(sr, start, end))
151
+			return sr;
152
+
153
+		/* Ok, try to lookup on the right side */
154
+		r = n->rb_right;
155
+		if (sr->lower <= end &&
156
+		    r && service_range_entry(r)->max >= start) {
157
+			n = r;
158
+			continue;
159
+		}
160
+		break;
161
+	}
162
+
163
+	return NULL;
164
+}
165
+
166
+/**
167
+ * service_range_match_next - find next service range matching a range
168
+ * @n: a node in service range rbtree from which the searching starts
169
+ * @start, end: the range (end >= start) for matching
170
+ *
171
+ * Return: the next service range node to the given node in the rbtree that
172
+ * overlaps the specific range if any. Otherwise, returns NULL.
173
+ */
174
+static struct service_range *service_range_match_next(struct rb_node *n,
175
+						      u32 start, u32 end)
176
+{
177
+	struct service_range *sr;
178
+	struct rb_node *p, *r;
179
+
180
+	while (n) {
181
+		r = n->rb_right;
182
+		if (r && service_range_entry(r)->max >= start)
183
+			/* A next overlap range node must be one in the right
184
+			 * subtree. If not, it has lower > end, then any next
185
+			 * successor (- an ancestor) of this node cannot
186
+			 * satisfy the condition either.
187
+			 */
188
+			return service_range_match_first(r, start, end);
189
+
190
+		/* No one in the right subtree can match, go up to find an
191
+		 * ancestor of this node which is parent of a left-hand child.
192
+		 */
193
+		while ((p = rb_parent(n)) && n == p->rb_right)
194
+			n = p;
195
+		if (!p)
196
+			break;
197
+
198
+		/* Return if this ancestor is an overlap */
199
+		sr = service_range_entry(p);
200
+		if (service_range_overlap(sr, start, end))
201
+			return sr;
202
+
203
+		/* Ok, try to lookup more from this ancestor */
204
+		if (sr->lower <= end) {
205
+			n = p;
206
+			continue;
207
+		}
208
+		break;
209
+	}
210
+
211
+	return NULL;
212
+}
83213 
84214 static int hash(int x)
85215 {
....@@ -109,6 +239,7 @@
109239 	INIT_LIST_HEAD(&publ->binding_node);
110240 	INIT_LIST_HEAD(&publ->local_publ);
111241 	INIT_LIST_HEAD(&publ->all_publ);
242
+	INIT_LIST_HEAD(&publ->list);
112243 	return publ;
113244 }
114245 
....@@ -135,84 +266,51 @@
135266 	return service;
136267 }
137268 
138
-/**
139
- * tipc_service_first_range - find first service range in tree matching instance
140
- *
141
- * Very time-critical, so binary search through range rb tree
142
- */
143
-static struct service_range *tipc_service_first_range(struct tipc_service *sc,
144
-						      u32 instance)
145
-{
146
-	struct rb_node *n = sc->ranges.rb_node;
147
-	struct service_range *sr;
148
-
149
-	while (n) {
150
-		sr = container_of(n, struct service_range, tree_node);
151
-		if (sr->lower > instance)
152
-			n = n->rb_left;
153
-		else if (sr->upper < instance)
154
-			n = n->rb_right;
155
-		else
156
-			return sr;
157
-	}
158
-	return NULL;
159
-}
160
-
161269 /*  tipc_service_find_range - find service range matching publication parameters
162270  */
163271 static struct service_range *tipc_service_find_range(struct tipc_service *sc,
164272 						     u32 lower, u32 upper)
165273 {
166
-	struct rb_node *n = sc->ranges.rb_node;
167274 	struct service_range *sr;
168275 
169
-	sr = tipc_service_first_range(sc, lower);
170
-	if (!sr)
171
-		return NULL;
172
-
173
-	/* Look for exact match */
174
-	for (n = &sr->tree_node; n; n = rb_next(n)) {
175
-		sr = container_of(n, struct service_range, tree_node);
176
-		if (sr->upper == upper)
177
-			break;
276
+	service_range_foreach_match(sr, sc, lower, upper) {
277
+		/* Look for exact match */
278
+		if (sr->lower == lower && sr->upper == upper)
279
+			return sr;
178280 	}
179
-	if (!n || sr->lower != lower || sr->upper != upper)
180
-		return NULL;
181281 
182
-	return sr;
282
+	return NULL;
183283 }
184284 
185285 static struct service_range *tipc_service_create_range(struct tipc_service *sc,
186286 						       u32 lower, u32 upper)
187287 {
188288 	struct rb_node **n, *parent = NULL;
189
-	struct service_range *sr, *tmp;
289
+	struct service_range *sr;
190290 
191291 	n = &sc->ranges.rb_node;
192292 	while (*n) {
193
-		tmp = container_of(*n, struct service_range, tree_node);
194293 		parent = *n;
195
-		tmp = container_of(parent, struct service_range, tree_node);
196
-		if (lower < tmp->lower)
197
-			n = &(*n)->rb_left;
198
-		else if (lower > tmp->lower)
199
-			n = &(*n)->rb_right;
200
-		else if (upper < tmp->upper)
201
-			n = &(*n)->rb_left;
202
-		else if (upper > tmp->upper)
203
-			n = &(*n)->rb_right;
294
+		sr = service_range_entry(parent);
295
+		if (lower == sr->lower && upper == sr->upper)
296
+			return sr;
297
+		if (sr->max < upper)
298
+			sr->max = upper;
299
+		if (lower <= sr->lower)
300
+			n = &parent->rb_left;
204301 		else
205
-			return tmp;
302
+			n = &parent->rb_right;
206303 	}
207304 	sr = kzalloc(sizeof(*sr), GFP_ATOMIC);
208305 	if (!sr)
209306 		return NULL;
210307 	sr->lower = lower;
211308 	sr->upper = upper;
309
+	sr->max = upper;
212310 	INIT_LIST_HEAD(&sr->local_publ);
213311 	INIT_LIST_HEAD(&sr->all_publ);
214312 	rb_link_node(&sr->tree_node, parent, n);
215
-	rb_insert_color(&sr->tree_node, &sc->ranges);
313
+	rb_insert_augmented(&sr->tree_node, &sc->ranges, &sr_callbacks);
216314 	return sr;
217315 }
218316 
....@@ -244,6 +342,8 @@
244342 	p = tipc_publ_create(type, lower, upper, scope, node, port, key);
245343 	if (!p)
246344 		goto err;
345
+	/* Suppose there shouldn't be a huge gap btw publs i.e. >INT_MAX */
346
+	p->id = sc->publ_cnt++;
247347 	if (in_own_node(net, node))
248348 		list_add(&p->local_publ, &sr->local_publ);
249349 	list_add(&p->all_publ, &sr->all_publ);
....@@ -278,6 +378,20 @@
278378 }
279379 
280380 /**
381
+ * Code reused: time_after32() for the same purpose
382
+ */
383
+#define publication_after(pa, pb) time_after32((pa)->id, (pb)->id)
384
+static int tipc_publ_sort(void *priv, struct list_head *a,
385
+			  struct list_head *b)
386
+{
387
+	struct publication *pa, *pb;
388
+
389
+	pa = container_of(a, struct publication, list);
390
+	pb = container_of(b, struct publication, list);
391
+	return publication_after(pa, pb);
392
+}
393
+
394
+/**
281395  * tipc_service_subscribe - attach a subscription, and optionally
282396  * issue the prescribed number of events if there is any service
283397  * range overlapping with the requested range
....@@ -286,36 +400,44 @@
286400 				   struct tipc_subscription *sub)
287401 {
288402 	struct tipc_subscr *sb = &sub->evt.s;
403
+	struct publication *p, *first, *tmp;
404
+	struct list_head publ_list;
289405 	struct service_range *sr;
290406 	struct tipc_name_seq ns;
291
-	struct publication *p;
292
-	struct rb_node *n;
293
-	bool first;
407
+	u32 filter;
294408 
295409 	ns.type = tipc_sub_read(sb, seq.type);
296410 	ns.lower = tipc_sub_read(sb, seq.lower);
297411 	ns.upper = tipc_sub_read(sb, seq.upper);
412
+	filter = tipc_sub_read(sb, filter);
298413 
299414 	tipc_sub_get(sub);
300415 	list_add(&sub->service_list, &service->subscriptions);
301416 
302
-	if (tipc_sub_read(sb, filter) & TIPC_SUB_NO_STATUS)
417
+	if (filter & TIPC_SUB_NO_STATUS)
303418 		return;
304419 
305
-	for (n = rb_first(&service->ranges); n; n = rb_next(n)) {
306
-		sr = container_of(n, struct service_range, tree_node);
307
-		if (sr->lower > ns.upper)
308
-			break;
309
-		if (!tipc_sub_check_overlap(&ns, sr->lower, sr->upper))
310
-			continue;
311
-		first = true;
312
-
420
+	INIT_LIST_HEAD(&publ_list);
421
+	service_range_foreach_match(sr, service, ns.lower, ns.upper) {
422
+		first = NULL;
313423 		list_for_each_entry(p, &sr->all_publ, all_publ) {
314
-			tipc_sub_report_overlap(sub, sr->lower, sr->upper,
315
-						TIPC_PUBLISHED,	p->port,
316
-						p->node, p->scope, first);
317
-			first = false;
424
+			if (filter & TIPC_SUB_PORTS)
425
+				list_add_tail(&p->list, &publ_list);
426
+			else if (!first || publication_after(first, p))
427
+				/* Pick this range's *first* publication */
428
+				first = p;
318429 		}
430
+		if (first)
431
+			list_add_tail(&first->list, &publ_list);
432
+	}
433
+
434
+	/* Sort the publications before reporting */
435
+	list_sort(NULL, &publ_list, tipc_publ_sort);
436
+	list_for_each_entry_safe(p, tmp, &publ_list, list) {
437
+		tipc_sub_report_overlap(sub, p->lower, p->upper,
438
+					TIPC_PUBLISHED, p->port, p->node,
439
+					p->scope, true);
440
+		list_del_init(&p->list);
319441 	}
320442 }
321443 
....@@ -390,7 +512,7 @@
390512 
391513 	/* Remove service range item if this was its last publication */
392514 	if (list_empty(&sr->all_publ)) {
393
-		rb_erase(&sr->tree_node, &sc->ranges);
515
+		rb_erase_augmented(&sr->tree_node, &sc->ranges, &sr_callbacks);
394516 		kfree(sr);
395517 	}
396518 
....@@ -438,34 +560,39 @@
438560 	rcu_read_lock();
439561 	sc = tipc_service_find(net, type);
440562 	if (unlikely(!sc))
441
-		goto not_found;
563
+		goto exit;
442564 
443565 	spin_lock_bh(&sc->lock);
444
-	sr = tipc_service_first_range(sc, instance);
445
-	if (unlikely(!sr))
446
-		goto no_match;
447
-
448
-	/* Select lookup algorithm: local, closest-first or round-robin */
449
-	if (*dnode == self) {
450
-		list = &sr->local_publ;
451
-		if (list_empty(list))
452
-			goto no_match;
453
-		p = list_first_entry(list, struct publication, local_publ);
454
-		list_move_tail(&p->local_publ, &sr->local_publ);
455
-	} else if (legacy && !*dnode && !list_empty(&sr->local_publ)) {
456
-		list = &sr->local_publ;
457
-		p = list_first_entry(list, struct publication, local_publ);
458
-		list_move_tail(&p->local_publ, &sr->local_publ);
459
-	} else {
460
-		list = &sr->all_publ;
461
-		p = list_first_entry(list, struct publication, all_publ);
462
-		list_move_tail(&p->all_publ, &sr->all_publ);
566
+	service_range_foreach_match(sr, sc, instance, instance) {
567
+		/* Select lookup algo: local, closest-first or round-robin */
568
+		if (*dnode == self) {
569
+			list = &sr->local_publ;
570
+			if (list_empty(list))
571
+				continue;
572
+			p = list_first_entry(list, struct publication,
573
+					     local_publ);
574
+			list_move_tail(&p->local_publ, &sr->local_publ);
575
+		} else if (legacy && !*dnode && !list_empty(&sr->local_publ)) {
576
+			list = &sr->local_publ;
577
+			p = list_first_entry(list, struct publication,
578
+					     local_publ);
579
+			list_move_tail(&p->local_publ, &sr->local_publ);
580
+		} else {
581
+			list = &sr->all_publ;
582
+			p = list_first_entry(list, struct publication,
583
+					     all_publ);
584
+			list_move_tail(&p->all_publ, &sr->all_publ);
585
+		}
586
+		port = p->port;
587
+		node = p->node;
588
+		/* Todo: as for legacy, pick the first matching range only, a
589
+		 * "true" round-robin will be performed as needed.
590
+		 */
591
+		break;
463592 	}
464
-	port = p->port;
465
-	node = p->node;
466
-no_match:
467593 	spin_unlock_bh(&sc->lock);
468
-not_found:
594
+
595
+exit:
469596 	rcu_read_unlock();
470597 	*dnode = node;
471598 	return port;
....@@ -488,7 +615,8 @@
488615 
489616 	spin_lock_bh(&sc->lock);
490617 
491
-	sr = tipc_service_first_range(sc, instance);
618
+	/* Todo: a full search i.e. service_range_foreach_match() instead? */
619
+	sr = service_range_match_first(sc->ranges.rb_node, instance, instance);
492620 	if (!sr)
493621 		goto no_match;
494622 
....@@ -517,7 +645,6 @@
517645 	struct service_range *sr;
518646 	struct tipc_service *sc;
519647 	struct publication *p;
520
-	struct rb_node *n;
521648 
522649 	rcu_read_lock();
523650 	sc = tipc_service_find(net, type);
....@@ -525,13 +652,7 @@
525652 		goto exit;
526653 
527654 	spin_lock_bh(&sc->lock);
528
-
529
-	for (n = rb_first(&sc->ranges); n; n = rb_next(n)) {
530
-		sr = container_of(n, struct service_range, tree_node);
531
-		if (sr->upper < lower)
532
-			continue;
533
-		if (sr->lower > upper)
534
-			break;
655
+	service_range_foreach_match(sr, sc, lower, upper) {
535656 		list_for_each_entry(p, &sr->local_publ, local_publ) {
536657 			if (p->scope == scope || (!exact && p->scope < scope))
537658 				tipc_dest_push(dports, 0, p->port);
....@@ -552,7 +673,6 @@
552673 	struct service_range *sr;
553674 	struct tipc_service *sc;
554675 	struct publication *p;
555
-	struct rb_node *n;
556676 
557677 	rcu_read_lock();
558678 	sc = tipc_service_find(net, type);
....@@ -560,13 +680,7 @@
560680 		goto exit;
561681 
562682 	spin_lock_bh(&sc->lock);
563
-
564
-	for (n = rb_first(&sc->ranges); n; n = rb_next(n)) {
565
-		sr = container_of(n, struct service_range, tree_node);
566
-		if (sr->upper < lower)
567
-			continue;
568
-		if (sr->lower > upper)
569
-			break;
683
+	service_range_foreach_match(sr, sc, lower, upper) {
570684 		list_for_each_entry(p, &sr->all_publ, all_publ) {
571685 			tipc_nlist_add(nodes, p->node);
572686 		}
....@@ -615,6 +729,7 @@
615729 	struct tipc_net *tn = tipc_net(net);
616730 	struct publication *p = NULL;
617731 	struct sk_buff *skb = NULL;
732
+	u32 rc_dests;
618733 
619734 	spin_lock_bh(&tn->nametbl_lock);
620735 
....@@ -629,12 +744,14 @@
629744 		nt->local_publ_count++;
630745 		skb = tipc_named_publish(net, p);
631746 	}
747
+	rc_dests = nt->rc_dests;
632748 exit:
633749 	spin_unlock_bh(&tn->nametbl_lock);
634750 
635751 	if (skb)
636
-		tipc_node_broadcast(net, skb);
752
+		tipc_node_broadcast(net, skb, rc_dests);
637753 	return p;
754
+
638755 }
639756 
640757 /**
....@@ -648,6 +765,7 @@
648765 	u32 self = tipc_own_addr(net);
649766 	struct sk_buff *skb = NULL;
650767 	struct publication *p;
768
+	u32 rc_dests;
651769 
652770 	spin_lock_bh(&tn->nametbl_lock);
653771 
....@@ -661,10 +779,11 @@
661779 		pr_err("Failed to remove local publication {%u,%u,%u}/%u\n",
662780 		       type, lower, upper, key);
663781 	}
782
+	rc_dests = nt->rc_dests;
664783 	spin_unlock_bh(&tn->nametbl_lock);
665784 
666785 	if (skb) {
667
-		tipc_node_broadcast(net, skb);
786
+		tipc_node_broadcast(net, skb, rc_dests);
668787 		return 1;
669788 	}
670789 	return 0;
....@@ -764,7 +883,7 @@
764883 			tipc_service_remove_publ(sr, p->node, p->key);
765884 			kfree_rcu(p, rcu);
766885 		}
767
-		rb_erase(&sr->tree_node, &sc->ranges);
886
+		rb_erase_augmented(&sr->tree_node, &sc->ranges, &sr_callbacks);
768887 		kfree(sr);
769888 	}
770889 	hlist_del_init_rcu(&sc->service_list);
....@@ -829,11 +948,11 @@
829948 		if (!hdr)
830949 			return -EMSGSIZE;
831950 
832
-		attrs = nla_nest_start(msg->skb, TIPC_NLA_NAME_TABLE);
951
+		attrs = nla_nest_start_noflag(msg->skb, TIPC_NLA_NAME_TABLE);
833952 		if (!attrs)
834953 			goto msg_full;
835954 
836
-		b = nla_nest_start(msg->skb, TIPC_NLA_NAME_TABLE_PUBL);
955
+		b = nla_nest_start_noflag(msg->skb, TIPC_NLA_NAME_TABLE_PUBL);
837956 		if (!b)
838957 			goto attr_msg_full;
839958