All of lore.kernel.org
 help / color / mirror / Atom feed
From: <nobuhiro1.iwamatsu@toshiba.co.jp>
To: <cip-dev@lists.cip-project.org>
Subject: RE: [cip-dev] New CVE entry this week
Date: Thu, 30 Sep 2021 06:33:06 +0000	[thread overview]
Message-ID: <TYAPR01MB625208BDE921AFB1D540B83D92AA9@TYAPR01MB6252.jpnprd01.prod.outlook.com> (raw)
In-Reply-To: <CAODzB9qObzKXuh+WaSqh_KD=T2NfZw79d-NnXFX1vmNGj5wsqQ@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 1421 bytes --]

Hi,


> -----Original Message-----
> From: cip-dev@lists.cip-project.org [mailto:cip-dev@lists.cip-project.org] On Behalf Of Masami Ichikawa
> Sent: Thursday, September 30, 2021 9:12 AM
> To: cip-dev <cip-dev@lists.cip-project.org>
> Subject: [cip-dev] New CVE entry this week
> 
> Hi !
> 
> It's this week's CVE report.
> 
> This week reported one new CVE.
> 
> * New CVEs
> 
> CVE-2021-20317: lib/timerqueue: Rely on rbtree semantics for next timer
> 
> This bug has been fixed in 5.4-rc1 so that before 5.4 kernels are
> affected. For 4.19, patch can be applied without any modification. For
> 4.4, it needs to modify patch to apply it.
> According to the description in
> cve.mitre.org(https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2021-20317),
> it describes "This flaw allows a local attacker with special user
> privileges to cause a denial of service" so I think this vulnerability
> severity may be low.
> 
> CVSS v3 score is not provided.
> 
> Fixed status
> 
> mainline: [511885d7061eda3eb1faf3f57dcc936ff75863f1]
> stable/5.10: [511885d7061eda3eb1faf3f57dcc936ff75863f1]
> stable/5.14: [511885d7061eda3eb1faf3f57dcc936ff75863f1]
> stable/5.4: [511885d7061eda3eb1faf3f57dcc936ff75863f1]

This commit can be applied directly to 4.14 and 4.19.
However, other LTSs need to be other commit or fixes.

I attached a patch for 4.14 and 4.19.

Best regards,
  Nobuhiro

[-- Attachment #2: 0001-lib-timerqueue-Rely-on-rbtree-semantics-for-next-tim.patch --]
[-- Type: application/octet-stream, Size: 4443 bytes --]

From eb343c7e4acbcd79517015b4ae992aa7b0e345cd Mon Sep 17 00:00:00 2001
From: Davidlohr Bueso <dave@stgolabs.net>
Date: Wed, 24 Jul 2019 08:23:23 -0700
Subject: [PATCH for 4.14 and 4.19] lib/timerqueue: Rely on rbtree semantics for next timer

commit 511885d7061eda3eb1faf3f57dcc936ff75863f1 upstream.

Simplify the timerqueue code by using cached rbtrees and rely on the tree
leftmost node semantics to get the timer with earliest expiration time.
This is a drop in conversion, and therefore semantics remain untouched.

The runtime overhead of cached rbtrees is be pretty much the same as the
current head->next method, noting that when removing the leftmost node,
a common operation for the timerqueue, the rb_next(leftmost) is O(1) as
well, so the next timer will either be the right node or its parent.
Therefore no extra pointer chasing. Finally, the size of the struct
timerqueue_head remains the same.

Passes several hours of rcutorture.

Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Link: https://lkml.kernel.org/r/20190724152323.bojciei3muvfxalm@linux-r8p5
Reference: CVE-2021-20317
Signed-off-by: Nobuhiro Iwamatsu (CIP) <nobuhiro1.iwamatsu@toshiba.co.jp>
---
 include/linux/timerqueue.h | 13 ++++++-------
 lib/timerqueue.c           | 30 ++++++++++++------------------
 2 files changed, 18 insertions(+), 25 deletions(-)

diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h
index 78b8cc73f12fc9..aff122f1062a83 100644
--- a/include/linux/timerqueue.h
+++ b/include/linux/timerqueue.h
@@ -12,8 +12,7 @@ struct timerqueue_node {
 };
 
 struct timerqueue_head {
-	struct rb_root head;
-	struct timerqueue_node *next;
+	struct rb_root_cached rb_root;
 };
 
 
@@ -29,13 +28,14 @@ extern struct timerqueue_node *timerqueue_iterate_next(
  *
  * @head: head of timerqueue
  *
- * Returns a pointer to the timer node that has the
- * earliest expiration time.
+ * Returns a pointer to the timer node that has the earliest expiration time.
  */
 static inline
 struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head)
 {
-	return head->next;
+	struct rb_node *leftmost = rb_first_cached(&head->rb_root);
+
+	return rb_entry(leftmost, struct timerqueue_node, node);
 }
 
 static inline void timerqueue_init(struct timerqueue_node *node)
@@ -45,7 +45,6 @@ static inline void timerqueue_init(struct timerqueue_node *node)
 
 static inline void timerqueue_init_head(struct timerqueue_head *head)
 {
-	head->head = RB_ROOT;
-	head->next = NULL;
+	head->rb_root = RB_ROOT_CACHED;
 }
 #endif /* _LINUX_TIMERQUEUE_H */
diff --git a/lib/timerqueue.c b/lib/timerqueue.c
index 0d54bcbc8170c7..7a8ae3d5fd4057 100644
--- a/lib/timerqueue.c
+++ b/lib/timerqueue.c
@@ -39,9 +39,10 @@
  */
 bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
 {
-	struct rb_node **p = &head->head.rb_node;
+	struct rb_node **p = &head->rb_root.rb_root.rb_node;
 	struct rb_node *parent = NULL;
-	struct timerqueue_node  *ptr;
+	struct timerqueue_node *ptr;
+	bool leftmost = true;
 
 	/* Make sure we don't add nodes that are already added */
 	WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
@@ -49,19 +50,17 @@ bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
 	while (*p) {
 		parent = *p;
 		ptr = rb_entry(parent, struct timerqueue_node, node);
-		if (node->expires < ptr->expires)
+		if (node->expires < ptr->expires) {
 			p = &(*p)->rb_left;
-		else
+		} else {
 			p = &(*p)->rb_right;
+			leftmost = false;
+		}
 	}
 	rb_link_node(&node->node, parent, p);
-	rb_insert_color(&node->node, &head->head);
+	rb_insert_color_cached(&node->node, &head->rb_root, leftmost);
 
-	if (!head->next || node->expires < head->next->expires) {
-		head->next = node;
-		return true;
-	}
-	return false;
+	return leftmost;
 }
 EXPORT_SYMBOL_GPL(timerqueue_add);
 
@@ -78,15 +77,10 @@ bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
 {
 	WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
 
-	/* update next pointer */
-	if (head->next == node) {
-		struct rb_node *rbn = rb_next(&node->node);
-
-		head->next = rb_entry_safe(rbn, struct timerqueue_node, node);
-	}
-	rb_erase(&node->node, &head->head);
+	rb_erase_cached(&node->node, &head->rb_root);
 	RB_CLEAR_NODE(&node->node);
-	return head->next != NULL;
+
+	return !RB_EMPTY_ROOT(&head->rb_root.rb_root);
 }
 EXPORT_SYMBOL_GPL(timerqueue_del);
 
-- 
2.33.0


WARNING: multiple messages have this Message-ID
From: "Nobuhiro Iwamatsu" <nobuhiro1.iwamatsu@toshiba.co.jp>
To: <cip-dev@lists.cip-project.org>
Subject: Re: [cip-dev] New CVE entry this week
Date: Thu, 30 Sep 2021 06:33:06 +0000	[thread overview]
Message-ID: <TYAPR01MB625208BDE921AFB1D540B83D92AA9@TYAPR01MB6252.jpnprd01.prod.outlook.com> (raw)
Message-ID: <20210930063306.Dm47sBrbyTNlujrjKESX2wVAlUKl6alf2B1URTsVNvM@z> (raw)
In-Reply-To: <CAODzB9qObzKXuh+WaSqh_KD=T2NfZw79d-NnXFX1vmNGj5wsqQ@mail.gmail.com>

[-- Attachment #1: Type: text/plain, Size: 1421 bytes --]

Hi,


> -----Original Message-----
> From: cip-dev@lists.cip-project.org [mailto:cip-dev@lists.cip-project.org] On Behalf Of Masami Ichikawa
> Sent: Thursday, September 30, 2021 9:12 AM
> To: cip-dev <cip-dev@lists.cip-project.org>
> Subject: [cip-dev] New CVE entry this week
> 
> Hi !
> 
> It's this week's CVE report.
> 
> This week reported one new CVE.
> 
> * New CVEs
> 
> CVE-2021-20317: lib/timerqueue: Rely on rbtree semantics for next timer
> 
> This bug has been fixed in 5.4-rc1 so that before 5.4 kernels are
> affected. For 4.19, patch can be applied without any modification. For
> 4.4, it needs to modify patch to apply it.
> According to the description in
> cve.mitre.org(https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2021-20317),
> it describes "This flaw allows a local attacker with special user
> privileges to cause a denial of service" so I think this vulnerability
> severity may be low.
> 
> CVSS v3 score is not provided.
> 
> Fixed status
> 
> mainline: [511885d7061eda3eb1faf3f57dcc936ff75863f1]
> stable/5.10: [511885d7061eda3eb1faf3f57dcc936ff75863f1]
> stable/5.14: [511885d7061eda3eb1faf3f57dcc936ff75863f1]
> stable/5.4: [511885d7061eda3eb1faf3f57dcc936ff75863f1]

This commit can be applied directly to 4.14 and 4.19.
However, other LTSs need to be other commit or fixes.

I attached a patch for 4.14 and 4.19.

Best regards,
  Nobuhiro

[-- Attachment #2: 0001-lib-timerqueue-Rely-on-rbtree-semantics-for-next-tim.patch --]
[-- Type: application/octet-stream, Size: 4443 bytes --]

From eb343c7e4acbcd79517015b4ae992aa7b0e345cd Mon Sep 17 00:00:00 2001
From: Davidlohr Bueso <dave@stgolabs.net>
Date: Wed, 24 Jul 2019 08:23:23 -0700
Subject: [PATCH for 4.14 and 4.19] lib/timerqueue: Rely on rbtree semantics for next timer

commit 511885d7061eda3eb1faf3f57dcc936ff75863f1 upstream.

Simplify the timerqueue code by using cached rbtrees and rely on the tree
leftmost node semantics to get the timer with earliest expiration time.
This is a drop in conversion, and therefore semantics remain untouched.

The runtime overhead of cached rbtrees is be pretty much the same as the
current head->next method, noting that when removing the leftmost node,
a common operation for the timerqueue, the rb_next(leftmost) is O(1) as
well, so the next timer will either be the right node or its parent.
Therefore no extra pointer chasing. Finally, the size of the struct
timerqueue_head remains the same.

Passes several hours of rcutorture.

Signed-off-by: Davidlohr Bueso <dbueso@suse.de>
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
Link: https://lkml.kernel.org/r/20190724152323.bojciei3muvfxalm@linux-r8p5
Reference: CVE-2021-20317
Signed-off-by: Nobuhiro Iwamatsu (CIP) <nobuhiro1.iwamatsu@toshiba.co.jp>
---
 include/linux/timerqueue.h | 13 ++++++-------
 lib/timerqueue.c           | 30 ++++++++++++------------------
 2 files changed, 18 insertions(+), 25 deletions(-)

diff --git a/include/linux/timerqueue.h b/include/linux/timerqueue.h
index 78b8cc73f12fc9..aff122f1062a83 100644
--- a/include/linux/timerqueue.h
+++ b/include/linux/timerqueue.h
@@ -12,8 +12,7 @@ struct timerqueue_node {
 };
 
 struct timerqueue_head {
-	struct rb_root head;
-	struct timerqueue_node *next;
+	struct rb_root_cached rb_root;
 };
 
 
@@ -29,13 +28,14 @@ extern struct timerqueue_node *timerqueue_iterate_next(
  *
  * @head: head of timerqueue
  *
- * Returns a pointer to the timer node that has the
- * earliest expiration time.
+ * Returns a pointer to the timer node that has the earliest expiration time.
  */
 static inline
 struct timerqueue_node *timerqueue_getnext(struct timerqueue_head *head)
 {
-	return head->next;
+	struct rb_node *leftmost = rb_first_cached(&head->rb_root);
+
+	return rb_entry(leftmost, struct timerqueue_node, node);
 }
 
 static inline void timerqueue_init(struct timerqueue_node *node)
@@ -45,7 +45,6 @@ static inline void timerqueue_init(struct timerqueue_node *node)
 
 static inline void timerqueue_init_head(struct timerqueue_head *head)
 {
-	head->head = RB_ROOT;
-	head->next = NULL;
+	head->rb_root = RB_ROOT_CACHED;
 }
 #endif /* _LINUX_TIMERQUEUE_H */
diff --git a/lib/timerqueue.c b/lib/timerqueue.c
index 0d54bcbc8170c7..7a8ae3d5fd4057 100644
--- a/lib/timerqueue.c
+++ b/lib/timerqueue.c
@@ -39,9 +39,10 @@
  */
 bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
 {
-	struct rb_node **p = &head->head.rb_node;
+	struct rb_node **p = &head->rb_root.rb_root.rb_node;
 	struct rb_node *parent = NULL;
-	struct timerqueue_node  *ptr;
+	struct timerqueue_node *ptr;
+	bool leftmost = true;
 
 	/* Make sure we don't add nodes that are already added */
 	WARN_ON_ONCE(!RB_EMPTY_NODE(&node->node));
@@ -49,19 +50,17 @@ bool timerqueue_add(struct timerqueue_head *head, struct timerqueue_node *node)
 	while (*p) {
 		parent = *p;
 		ptr = rb_entry(parent, struct timerqueue_node, node);
-		if (node->expires < ptr->expires)
+		if (node->expires < ptr->expires) {
 			p = &(*p)->rb_left;
-		else
+		} else {
 			p = &(*p)->rb_right;
+			leftmost = false;
+		}
 	}
 	rb_link_node(&node->node, parent, p);
-	rb_insert_color(&node->node, &head->head);
+	rb_insert_color_cached(&node->node, &head->rb_root, leftmost);
 
-	if (!head->next || node->expires < head->next->expires) {
-		head->next = node;
-		return true;
-	}
-	return false;
+	return leftmost;
 }
 EXPORT_SYMBOL_GPL(timerqueue_add);
 
@@ -78,15 +77,10 @@ bool timerqueue_del(struct timerqueue_head *head, struct timerqueue_node *node)
 {
 	WARN_ON_ONCE(RB_EMPTY_NODE(&node->node));
 
-	/* update next pointer */
-	if (head->next == node) {
-		struct rb_node *rbn = rb_next(&node->node);
-
-		head->next = rb_entry_safe(rbn, struct timerqueue_node, node);
-	}
-	rb_erase(&node->node, &head->head);
+	rb_erase_cached(&node->node, &head->rb_root);
 	RB_CLEAR_NODE(&node->node);
-	return head->next != NULL;
+
+	return !RB_EMPTY_ROOT(&head->rb_root.rb_root);
 }
 EXPORT_SYMBOL_GPL(timerqueue_del);
 
-- 
2.33.0


[-- Attachment #3: Type: text/plain, Size: 429 bytes --]


-=-=-=-=-=-=-=-=-=-=-=-
Links: You receive all messages sent to this group.
View/Reply Online (#6764): https://lists.cip-project.org/g/cip-dev/message/6764
Mute This Topic: https://lists.cip-project.org/mt/85963258/4520388
Group Owner: cip-dev+owner@lists.cip-project.org
Unsubscribe: https://lists.cip-project.org/g/cip-dev/leave/10495289/4520388/727948398/xyzzy [cip-dev@archiver.kernel.org]
-=-=-=-=-=-=-=-=-=-=-=-


  reply	other threads:[~2021-09-30  6:33 UTC|newest]

Thread overview: 27+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-09-30  0:12 Masami Ichikawa
2021-09-30  0:12 ` [cip-dev] " Masami Ichikawa
2021-09-30  6:33 ` nobuhiro1.iwamatsu [this message]
2021-09-30  6:33   ` Nobuhiro Iwamatsu
2021-09-30 12:11   ` Masami Ichikawa
2021-09-30 12:11     ` Masami Ichikawa
  -- strict thread matches above, loose matches on Subject: below --
2021-10-21  1:21 Masami Ichikawa
2021-10-21  8:41 ` [cip-dev] " nobuhiro1.iwamatsu
2021-10-21 12:05   ` Masami Ichikawa
2021-10-13 23:54 Masami Ichikawa
2021-10-13 23:54 ` Masami Ichikawa
2021-10-14  6:55   ` Pavel Machek
2021-10-14  6:55     ` Pavel Machek
2021-10-07  0:59 Masami Ichikawa
2021-10-07  0:59 ` Masami Ichikawa
2021-10-07  7:30   ` Pavel Machek
2021-10-07  7:30     ` Pavel Machek
2021-10-07 11:38     ` Masami Ichikawa
2021-10-07 11:38       ` Masami Ichikawa
2021-09-23  1:52 Masami Ichikawa
2021-09-16  0:43 Masami Ichikawa
2021-09-16  4:55 ` Nobuhiro Iwamatsu
2021-09-09  2:39 Masami Ichikawa
2021-09-09  6:41 ` Pavel Machek
2021-09-09 12:23   ` Masami Ichikawa
     [not found] ` <CAMLqsBZCbrdOaxhuc81kvZsinS+_bFPp2tpmuVnczC1EXCA3Zg@mail.gmail.com>
2021-09-10  0:40   ` Masami Ichikawa
2021-09-02  1:05 Masami Ichikawa
2021-09-02  6:27 ` Pavel Machek
2021-09-02  7:10   ` Nobuhiro Iwamatsu
2021-09-02 12:17   ` Masami Ichikawa

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=TYAPR01MB625208BDE921AFB1D540B83D92AA9@TYAPR01MB6252.jpnprd01.prod.outlook.com \
    --to=nobuhiro1.iwamatsu@toshiba.co.jp \
    --cc=cip-dev@lists.cip-project.org \
    --subject='RE: [cip-dev] New CVE entry this week' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.