Received-SPF: pass (google.com: domain of linux-kernel+bounces-72677-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.199.223 as permitted sender) client-ip=147.75.199.223;
Date: Tue, 20 Feb 2024 17:17:45 +0800
From: Chen Yu <yu.c.chen@intel.com>
To: Abel Wu <wuyun.abel@bytedance.com>
CC: kernel test robot <oliver.sang@intel.com>, <oe-lkp@lists.linux.dev>,
	<lkp@intel.com>, <linux-kernel@vger.kernel.org>, Peter Zijlstra
	<peterz@infradead.org>, <aubrey.li@linux.intel.com>, Tiwei Bie
	<tiwei.btw@antgroup.com>, Honglei Wang <wanghonglei@didichuxing.com>, "Aaron
 Lu" <aaron.lu@intel.com>
Subject: Re: Re: [linus:master] [sched/eevdf] 2227a957e1:
 BUG:kernel_NULL_pointer_dereference,address
Message-ID: <ZdRuOQazh0KkK8CD@chenyu5-mobl2>
References: <202401301012.2ed95df0-oliver.sang@intel.com>
 <23cbb613-c8a2-4f07-b83b-fa3104bef642@bytedance.com>
 <ZdNOb7fOLIoY5sgW@chenyu5-mobl2>
 <9d8cf754-86ad-491f-9c3b-cca9efb2f5b2@bytedance.com>
Content-Type: text/plain; charset="us-ascii"
Content-Disposition: inline
In-Reply-To: <9d8cf754-86ad-491f-9c3b-cca9efb2f5b2@bytedance.com>
Precedence: bulk
MIME-Version: 1.0
X-MS-Exchange-AntiSpam-MessageData-ChunkCount: 1
X-MS-Exchange-AntiSpam-MessageData-0: =?us-ascii?Q?QSi4e9Rq9keIlQlcUPI5PPmMO/6G+U/0B52hAgxP4he59s/g0kuKBti43s2G?=
 =?us-ascii?Q?FBSgYp/0VPsaRvXxN5I/8V7ioKNChq95K5xnuAnBl/nnqqvPAXdlmZTxIojQ?=
 =?us-ascii?Q?UdFrNfLE366MP/R19AXsFuA7DmfuUEBBZkMb433bVg1I9OjX0OMeb3bxhqvc?=
 =?us-ascii?Q?LIbylG88AxfE0TG2dk/PmGKe5fTwwriryIpnSWa6cPlGzzNMGjYweZNo1ALH?=
 =?us-ascii?Q?xQx2cvM33hVt3hIJ7dklWjxgNaCbFyG+FxVcE3yiymn+OGtoSms1OCLql8FE?=
 =?us-ascii?Q?KxG8CiS7GNuA8BjOr3sXdiwVby92H7mi7q7BgJMhB7GMx32xks2YYwldGQZC?=
 =?us-ascii?Q?d5mhMn8SlZwbBhGfmiIiJniQ4poOal1lTCO5hSkxFlmSJNJOFLd6GgsOdIYI?=
 =?us-ascii?Q?j/jB03MnMZSgaFNAefSSnoYCGOIDFB9t5oVDM6Zi9QIfAj7QdetOHgB9Smb/?=
 =?us-ascii?Q?OSZy0C0cnmOT4bMHU2F2pS3PA0jBoYz1i5Fw/oMMwcYVUjoIxwIUrVbpFfAc?=
 =?us-ascii?Q?sLCOl9euZEgYLM+tk+wOYj4OHSjTdKd8a9WR8RNSc2lkfC180x8iFoZ1dXtr?=
 =?us-ascii?Q?KEKJC078RrgbNIHoopQNR6gOlbYjYQX9Qj+kUMGz7AkZMNB6vujIxDTFPIKg?=
 =?us-ascii?Q?4kjcqAP02beNgKvR7Db/iBBTrqxaP6CkyK04aa6ivmgCqb5eoLt4+bEhRWGT?=
 =?us-ascii?Q?5PAvFB4N4Gth6WFe5df5XLI1uVXS82Hmtqur/0Vp//w2xZA20waRPRssW+aQ?=
 =?us-ascii?Q?ULzhGMj98vPQLk8gliy2NqUicy/+cmSK0VTgqvAw/NtF85/VqQkvPQ0IrbcW?=
 =?us-ascii?Q?aYp+AWDbR+07vMXpUbfnFfDrHEYFhibWb4hJHWCvkb8CKn/K7hztL3003v0t?=
 =?us-ascii?Q?7aZKCObJX49J+tzOSe0e867+XYGM9mBP3fu6Uepifqicn61GQLrredC5ELn9?=
 =?us-ascii?Q?GI2kHTrGNuQm7zoSMQ+Hd4qbWk1kUR0OhdHsj0/TRdJVgTDDANiBajl4vrUm?=
 =?us-ascii?Q?0NBtZffo7M7ixqWYiz7XMHWkvcLhLFERXdB5btJ0SEu+s1SIlcAfth19zKcc?=
 =?us-ascii?Q?4igDmatH088tjU80jx2XL+ZBU8DRcKHBAkKyqWnF0AOSxYv/T5nt0qvWGnxB?=
 =?us-ascii?Q?d6uMvX6F0pTfdtC0sIAG5mYdFy1+CZ+JrApwPSv9ZtN/DN0wzG18l/936d2U?=
 =?us-ascii?Q?78Ph2hD6ENLTr82u2muQQ8kJqGsW61begqili9fXsljgrSkY8djqitAZ0MD0?=
 =?us-ascii?Q?EWW4weKZjxhSVJhkZ77Izqjd7LnYiEeZaFGd1wL+H/6Ywji2Otu+J7xYoro4?=
 =?us-ascii?Q?w4BkQDrYw8Zj53Zi1qQupXX0FLg1Ki1lpb4jLCfaKpOtfH/9EDTQT0e2M4Vi?=
 =?us-ascii?Q?GgIxH+0OwmhGGpIzPOoQuL6IgZKgN/8JU+tQmCxlkKJ1RhvoSxZMIvmZqIrs?=
 =?us-ascii?Q?UOsXbaACQv5IfnPdxgFf8Y4ssU6Ktv3y6RBBvR5ah390IuIYgxksC2zlv91v?=
 =?us-ascii?Q?xcY36MDQvJmfPa0GJGOVfyXGT8tZzj+aif1v05SmlmkLz9MuiXloVbx4DgTU?=
 =?us-ascii?Q?qWfqrqKecGDfKaNOg8nWuV5jSKF3r4jhMVRLkBZ0?=
X-MS-Exchange-CrossTenant-Network-Message-Id: 1f8536a2-60c8-419e-fa55-08dc31f4d3c3
X-MS-Exchange-CrossTenant-AuthSource: DM4PR11MB6020.namprd11.prod.outlook.com
X-MS-Exchange-CrossTenant-AuthAs: Internal
X-MS-Exchange-CrossTenant-OriginalArrivalTime: 20 Feb 2024 09:17:57.5365
 (UTC)
X-MS-Exchange-CrossTenant-FromEntityHeader: Hosted
X-MS-Exchange-CrossTenant-Id: 46c98d88-e344-4ed4-8496-4ed7712e255d
X-MS-Exchange-CrossTenant-MailboxType: HOSTED
X-MS-Exchange-CrossTenant-UserPrincipalName: wxW3azawAcz9+1w/Ydx+IHAjDdqJh0pVO7ms9L/dSZ96Ihv6pYEvZM+QG7SUCwkuTcPFPvIBNjfZPyyHCGcfTA==
X-MS-Exchange-Transport-CrossTenantHeadersStamped: DS0PR11MB6374
X-OriginatorOrg: intel.com

On 2024-02-20 at 12:04:33 +0800, Abel Wu wrote:
> On 2/19/24 8:49 PM, Chen Yu Wrote:
> > 
> > While looking at pick_eevdf(), I have a thought.
> > Currently the sched entity is sorted by their deadline. During task
> > pickup, the pick_eevdf() scans for an candidate sched entity with the
> > smallest deadline. Meanwhile this candidate sched entity must also be
> > eligible.
> > 
> > The scan is O(lgn) on average, and O(1) at best case. How about making the
> > average scan even faster by sorting the sched entity not only by deadline,
> > but also the eligibility? The idea is that, the eligible sched entity with
> > smaller deadline is sorted at the front the tree. Otherwise, if the entity
> > is not eligible, even if it has a smaller deadline, it should be sorted
> > at the end of the tree.
> 
> Eligibility is dynamic due to the nature of weighted average vruntime.
> IIUC if doing so like above, update_curr() should take the responsibility
> to re-sort the tree which seems to be O(logN).
> 
> > 
> > After the change, pick_eevdf() get the leftmost sched entity at O(1) on
> > average. Besides, it is guaranteed to return non-NULL sched entity in
> > pick_eevdf(), which prevents suspicious NULL pointer exception in pick_eevdf().
> 
> It is guaranteed when doing pick that the rbtree is non-NULL, and given
> that rq lock is held, I don't think the bug is inside pick_eevdf().
>

That's true, my suspect is that although the tree is not NULL, the eligible
check might return false negative thus no candidate is chosen, and pick_eevdf()
is the victim of that. Previously commit 8dafa9d0eb1a ("sched/eevdf: Fix min_deadline
heap integrity") did similar thing to fix the min_deadline. Without this change,
the tree might be traversed incorrectly and found a NULL candidate. And this is
why I'm thinking of printing the whole tree when NULL entity is chosen in
pick_eevdf().

thanks,
Chenyu