Hi all,
When I debug rb-tree related patches, it's easily to trigger panic for my rb-tree code, I try to use below simple pseudo code to demonstrate it:
detach_tasks() node = rb_first(&env->src_rq->seq_node); -> 'node_prev' while(node) { se = rb_entry(node, struct sched_entity, seq_node); node = rb_next(&se->seq_node); -> 'node_next'
if (balanced) break; if (meet_conditions_for_migration) detach_task(se); -> Other CPU acquires src_rq lock -> and remove 'node_next' firstly else continue;
}
In this flow the detach_task() has been modified by WALT patches, so in function detach_task() it releases lock for source rq in function double_lock_balance(env->src_rq, env->dst_rq) and then acquire source rq and destination rq lock in specific sequence so avoid recursive deadlock; But this gives other CPUs chance to acquire lock for souce rq and remove node_next from the rb tree, e.g. it is possible to dequeue the corresponding task on any other CPU (Like CPU_B).
Detach_tasks() will continue iteration for 'node_next', and 'node_next' can meet the condition to detach, so it try to remove 'node_next' from rb tree, but 'node_next' has been removed yet by CPU_B. So finally introduce panic. Please see enclosed kernel log.
So essentially it's unsafe to release and acquire again for rq lock when scheduler is iterating the lists/tree for the rq. But this code is delibrately written for WALT to update souce rq and destination rq statistics for workload. So currently I can simply revert double_lock_balance()/double_unlock_balance() for only using PELT signals, but for WALT I want to get some suggestion for the fixing, if we confirm this is a potential issue, this issue should exist both on Android common kernel 3.18 and 4.4.
/* * detach_task() -- detach the task for the migration specified in env */ static void detach_task(struct task_struct *p, struct lb_env *env) { lockdep_assert_held(&env->src_rq->lock);
deactivate_task(env->src_rq, p, 0); p->on_rq = TASK_ON_RQ_MIGRATING; double_lock_balance(env->src_rq, env->dst_rq); set_task_cpu(p, env->dst_cpu); double_unlock_balance(env->src_rq, env->dst_rq); }
Thanks, Leo Yan
Hi Leo,
On 15-Nov 22:05, Leo Yan wrote:
Hi all,
When I debug rb-tree related patches, it's easily to trigger panic for my rb-tree code, I try to use below simple pseudo code to demonstrate it:
detach_tasks() node = rb_first(&env->src_rq->seq_node); -> 'node_prev' while(node) { se = rb_entry(node, struct sched_entity, seq_node); node = rb_next(&se->seq_node); -> 'node_next'
if (balanced) break; if (meet_conditions_for_migration) detach_task(se); -> Other CPU acquires src_rq lock -> and remove 'node_next' firstly else continue;
}
In this flow the detach_task() has been modified by WALT patches, so in function detach_task() it releases lock for source rq in function double_lock_balance(env->src_rq, env->dst_rq) and then acquire source rq and destination rq lock in specific sequence so avoid recursive deadlock; But this gives other CPUs chance to acquire lock for souce rq and remove node_next from the rb tree, e.g. it is possible to dequeue the corresponding task on any other CPU (Like CPU_B).
Detach_tasks() will continue iteration for 'node_next', and 'node_next' can meet the condition to detach, so it try to remove 'node_next' from rb tree, but 'node_next' has been removed yet by CPU_B. So finally introduce panic. Please see enclosed kernel log.
So essentially it's unsafe to release and acquire again for rq lock when scheduler is iterating the lists/tree for the rq.
I'm wondering if your rb_tree usage can be extended to be lockless. This should be achievable by properly using reference couting for each node, thus marking a node as "in use" right after your rb_bext call, or better using RCU to protect the reader side.
This last option would be ultimately a better and more generic solution but it can became quite complex. You should still be able to find some exaple of RCU-protected rb-trees... in the past this technique has been already used for example by Nick Piggin in it's fully lockless dentry search [1] back in the 2011.
But this code is delibrately written for WALT to update souce rq and destination rq statistics for workload. So currently I can simply revert double_lock_balance()/double_unlock_balance() for only using PELT signals, but for WALT I want to get some suggestion for the fixing, if we confirm this is a potential issue, this issue should exist both on Android common kernel 3.18 and 4.4.
AFAIK, in the (simplified) version of WALT posted on LKML before LPC [2] Vikram got ride of all the double loking. If the problem you reported is verified, than we should probably try to update AOSP WALT using the same locking schema used by the LKML posting.
[1] http://www2.comp.ufscar.br/lxr/source/Documentation/RCU/RTFP.txt#L176 [2] https://lkml.org/lkml/2016/10/28/84
Cheers Patrick
/*
- detach_task() -- detach the task for the migration specified in env
*/ static void detach_task(struct task_struct *p, struct lb_env *env) { lockdep_assert_held(&env->src_rq->lock);
deactivate_task(env->src_rq, p, 0); p->on_rq = TASK_ON_RQ_MIGRATING; double_lock_balance(env->src_rq, env->dst_rq); set_task_cpu(p, env->dst_cpu); double_unlock_balance(env->src_rq, env->dst_rq);}
Thanks, Leo Yan
hikey:/data # time sh -c 'for i in `seq 100`; do ./hackbench -p -P > /dev/null'for i in `seq 100`; do ./hackbench -p -P > /dev/null <; done'[ 21.285294] type=1400 audit(25.523:9): avc: denied { dac_override } for pid=1744 comm="healthd" capability=1 scontext=u:r:healthd:s0 tcontext=u:r:healthd:s0 tclass=capability permissive=1 [ 21.285334] healthd: battery l=100 v=0 t=42.4 h=2 st=2 chg=a [ 21.733755] lowmemorykiller: lowmem_shrink: convert oom_adj to oom_score_adj: [ 21.741081] lowmemorykiller: oom_adj 0 => oom_score_adj 0 [ 21.746636] lowmemorykiller: oom_adj 1 => oom_score_adj 58 [ 21.752242] lowmemorykiller: oom_adj 2 => oom_score_adj 117 [ 21.757919] lowmemorykiller: oom_adj 3 => oom_score_adj 176 [ 21.763571] lowmemorykiller: oom_adj 9 => oom_score_adj 529 [ 21.769245] lowmemorykiller: oom_adj 15 => oom_score_adj 1000
[ 22.621594] acc_open [ 22.623878] acc_release [ 24.178591] FAT-fs (mmcblk1p1): Volume was not properly unmounted. Some data may be corrupt. Please run fsck. [ 24.495649] Unable to handle kernel NULL pointer dereference at virtual address 00000000 [ 24.503860] pgd = ffffffc017be0000 [ 24.507294] [00000000] *pgd=0000000017be1003, *pud=0000000017be1003, *pmd=0000000000000000 [ 24.515661] Internal error: Oops: 96000046 [#1] PREEMPT SMP [ 24.521296] CPU: 6 PID: 3028 Comm: hackbench Not tainted 4.4.17-230077-g0f6b622-dirty #134 [ 24.529645] Hardware name: HiKey Development Board (DT) [ 24.534922] task: ffffffc017008080 ti: ffffffc017d70000 task.ti: ffffffc017d70000 [ 24.542491] PC is at rb_erase+0x1a4/0x394 [ 24.546544] LR is at dequeue_task_fair+0x34c/0x1674 [ 24.551469] pc : [<ffffffc0004c4550>] lr : [<ffffffc0000f6f60>] pstate: 600001c5 [ 24.558940] sp : ffffffc017d738e0 [ 24.562284] x29: ffffffc017d738e0 x28: ffffffc01694f260 [ 24.567655] x27: ffffffc0365f1a00 x26: 0000000039b9fd7b [ 24.573025] x25: 00000000313bb52c x24: ffffffc0365f1a00 [ 24.578394] x23: 0000000000000007 x22: ffffffc017d70000 [ 24.583764] x21: 0000000000000000 x20: ffffffc01694f3d8 [ 24.589135] x19: ffffffc01854e0f0 x18: 0000000000000000 [ 24.594505] x17: 0000000000000001 x16: ffffffc000218048 [ 24.599876] x15: 00000000004a49a8 x14: 2d2d2d2d2d2d2d2d [ 24.605246] x13: 2d2d2d2d2d2d2d2d x12: 2d2d2d2d2d2d2d2d [ 24.610616] x11: ffffffc0365f1a60 x10: 0000000000000001 [ 24.615986] x9 : 0000000000000001 x8 : 0000000000000000 [ 24.621355] x7 : 0000000000000007 x6 : ffffffc0172ba3f0 [ 24.626726] x5 : 0000000000000000 x4 : 0000000000000000 [ 24.632097] x3 : ffffffc016b68571 x2 : ffffffc016b68570 [ 24.637466] x1 : ffffffc0365f1a28 x0 : ffffffc0172ba3f0 [ 24.642838] [ 24.642838] PC: 0xffffffc0004c44d0: [ 24.647850] 44d0 f27ef463 540009e0 f9400865 eb05005f 540009e0 f9000460 aa0403e0 f9400404 [ 24.656144] 44f0 b4000064 f9400083 36000ae3 f9400803 b4000063 f9400064 36000d24 f9000002 [ 24.664437] 4510 f9400040 360008a0 f27ef400 54fff920 aa0203e3 aa0003e2 f9400440 eb03001f [ 24.672729] 4530 54fffbc1 f9400840 f9400003 37000203 f9400404 b2400043 f9000844 f9000402 [ 24.681022] 4550 f9000083 f9400043 f9000003 f9000040 f27ef463 54000b80 f9400865 eb05005f [ 24.689315] 4570 54000b80 f9000460 aa0403e0 f9400804 b4000064 f9400083 36000d03 f9400403 [ 24.697608] 4590 b4fffbe3 f9400064 3707fba4 f9400864 f9000404 f9000860 f9000843 b4000064 [ 24.705901] 45b0 b2400005 f9000085 aa0003e4 aa0303e0 f9400405 b2400066 f9000845 f9000402 [ 24.714195] [ 24.714195] LR: 0xffffffc0000f6ee0: [ 24.719207] 6ee0 b0008500 91044000 f9401419 b4000139 f9400323 d1018397 f9400720 aa1403e2 [ 24.727501] 6f00 aa1703e1 d63f0060 f8418f23 b5ffff63 b9401ac0 51000400 b9001ac0 35fff5c0 [ 24.735794] 6f20 f94002c0 360ff580 942b3e62 17ffffaa aa1b03e0 aa1c03e1 97fff4d2 f9401f60 [ 24.744087] 6f40 eb00039f 540000e0 f9401b73 91004380 9100a361 eb00027f 54004160 940f3514 [ 24.752380] 6f60 aa1c03e1 aa1b03e0 b900539f 97fff3ef f9403780 f9401361 cb010000 f9003780 [ 24.760671] 6f80 17ffffba d0005740 b9401ec1 6b1f003f f944e802 1100fc20 1a81b000 13067c00 [ 24.768964] 6fa0 f860d840 9ac12401 3607f181 b9401ac0 11000400 b9001ac0 b0008500 91038000 [ 24.777256] 6fc0 f9401414 b4000114 f9400283 f9400680 aa1803e2 2a1303e1 d63f0060 f8418e83 [ 24.785549] [ 24.785549] SP: 0xffffffc017d73860: [ 24.790562] 3860 1694f3d8 ffffffc0 00000000 00000000 17d70000 ffffffc0 00000007 00000000 [ 24.798855] 3880 365f1a00 ffffffc0 313bb52c 00000000 39b9fd7b 00000000 365f1a00 ffffffc0 [ 24.807147] 38a0 1694f260 ffffffc0 17d738e0 ffffffc0 000f6f60 ffffffc0 17d738e0 ffffffc0 [ 24.815440] 38c0 004c4550 ffffffc0 600001c5 00000000 00000000 00000000 1694f260 ffffffc0 [ 24.823733] 38e0 17d73990 ffffffc0 000eaed4 ffffffc0 3df78200 ffffffc0 1694f200 ffffffc0 [ 24.832026] 3900 00000002 00000000 00000140 00000000 17d73b10 ffffffc0 01072000 ffffffc0 [ 24.840319] 3920 00000001 00000000 01071130 ffffffc0 1694f200 ffffffc0 1694f288 ffffffc0 [ 24.848612] 3940 17d73950 00000000 3df78200 ffffffc0 00be1558 ffffffc0 00000400 00000000 [ 24.856905] [ 24.856905] X0: 0xffffffc0172ba370: [ 24.861918] a370 1e44dbd3 00e00000 1e4cebd3 00e00000 00000000 00000000 17c64000 ffffffc0 [ 24.870211] a390 00000002 00004040 00000000 00000000 00000000 00000000 00000000 00000008 [ 24.878502] a3b0 fffef292 00000000 35156f00 ffffffc0 00000004 00000001 00000078 00000078 [ 24.886795] a3d0 00000078 00000000 00be1588 ffffffc0 00000400 00000000 00400000 00000000 [ 24.895086] a3f0 16b68570 ffffffc0 16b68570 ffffffc0 00000000 00000000 1732c389 ffffffc0 [ 24.903379] a410 1738f008 ffffffc0 172bb108 ffffffc0 172ba420 ffffffc0 172ba420 ffffffc0 [ 24.911672] a430 00000001 00000000 b358d756 00000005 002ddbb4 00000000 069a4208 00000000 [ 24.919966] a450 00210a0b 00000000 00000003 00000000 b35909fe 00000005 03efb0c1 00000000 [ 24.928260] [ 24.928260] X1: 0xffffffc0365f19a8: [ 24.933273] 19a8 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 [ 24.941566] 19c8 2cf4d220 ffffffc0 00000000 00000000 365f19d8 ffffffc0 365f19d8 ffffffc0 [ 24.949859] 19e8 365f19e8 ffffffc0 365f19e8 ffffffc0 2cfe84b0 ffffffc0 00005000 00000000 [ 24.958151] 1a08 00000000 00000000 00000014 00000014 195a1086 00000000 06bb45fa 00000000 [ 24.966443] 1a28 1854edf0 ffffffc0 1854e0f0 ffffffc0 00000000 00000000 00000000 00000000 [ 24.974737] 1a48 00000000 00000000 00000000 00000000 00000000 00000000 b40d5f5c 00000005 [ 24.983030] 1a68 39b9fd7b 00000000 01d8655b 000002f5 00004e3c 00000000 00000288 00000000 [ 24.991322] 1a88 2f819847 00000000 0000404c 00000000 00004e3c 00000000 00000000 00000000 [ 24.999616] [ 24.999616] X2: 0xffffffc016b684f0: [ 25.004628] 84f0 01b0ee88 00000017 01b0ee8c 00000017 00000000 00000000 16b30000 ffffffc0 [ 25.012921] 8510 00000002 00004040 00000000 00000000 00000000 00000000 00000000 0000001c [ 25.021215] 8530 fffef292 00000000 17c01280 ffffffc0 00000004 00000001 00000078 00000078 [ 25.029507] 8550 00000078 00000000 00be1588 ffffffc0 00000400 00000000 00400000 00000000 [ 25.037799] 8570 1738eff1 ffffffc0 00000000 00000000 00000000 00000000 184bce89 ffffffc0 [ 25.046092] 8590 00000000 00000000 00000000 00000000 16b685a0 ffffffc0 16b685a0 ffffffc0 [ 25.054385] 85b0 00000001 00000000 b3e87752 00000005 002ef47a 00000000 069c1db4 00000000 [ 25.062677] 85d0 00263c6b 00000000 00000002 00000000 b3f6628d 00000005 04e6a0b1 00000000 [ 25.070971] [ 25.070971] X3: 0xffffffc016b684f1: [ 25.075984] 84f0 01b0ee88 00000017 01b0ee8c 00000017 00000000 00000000 16b30000 ffffffc0 [ 25.084277] 8510 00000002 00004040 00000000 00000000 00000000 00000000 00000000 0000001c [ 25.092569] 8530 fffef292 00000000 17c01280 ffffffc0 00000004 00000001 00000078 00000078 [ 25.100862] 8550 00000078 00000000 00be1588 ffffffc0 00000400 00000000 00400000 00000000 [ 25.109154] 8570 1738eff1 ffffffc0 00000000 00000000 00000000 00000000 184bce89 ffffffc0 [ 25.117447] 8590 00000000 00000000 00000000 00000000 16b685a0 ffffffc0 16b685a0 ffffffc0 [ 25.125740] 85b0 00000001 00000000 b3e87752 00000005 002ef47a 00000000 069c1db4 00000000 [ 25.134032] 85d0 00263c6b 00000000 00000002 00000000 b3f6628d 00000005 04e6a0b1 00000000 [ 25.142324] 85f0 00000005 00000000 099a1500 00000000 00000000 00000000 00000000 00000000 [ 25.150619] [ 25.150619] X6: 0xffffffc0172ba370: [ 25.155632] a370 1e44dbd3 00e00000 1e4cebd3 00e00000 00000000 00000000 17c64000 ffffffc0 [ 25.163926] a390 00000002 00004040 00000000 00000000 00000000 00000000 00000000 00000008 [ 25.172217] a3b0 fffef292 00000000 35156f00 ffffffc0 00000004 00000001 00000078 00000078 [ 25.180510] a3d0 00000078 00000000 00be1588 ffffffc0 00000400 00000000 00400000 00000000 [ 25.188803] a3f0 16b68570 ffffffc0 16b68570 ffffffc0 00000000 00000000 1732c389 ffffffc0 [ 25.197095] a410 1738f008 ffffffc0 172bb108 ffffffc0 172ba420 ffffffc0 172ba420 ffffffc0 [ 25.205388] a430 00000001 00000000 b358d756 00000005 002ddbb4 00000000 069a4208 00000000 [ 25.213680] a450 00210a0b 00000000 00000003 00000000 b35909fe 00000005 03efb0c1 00000000 [ 25.221975] [ 25.221975] X11: 0xffffffc0365f19e0: [ 25.227076] 19e0 365f19d8 ffffffc0 365f19e8 ffffffc0 365f19e8 ffffffc0 2cfe84b0 ffffffc0 [ 25.235369] 1a00 00005000 00000000 00000000 00000000 00000014 00000014 195a1086 00000000 [ 25.243661] 1a20 06bb45fa 00000000 1854edf0 ffffffc0 1854e0f0 ffffffc0 00000000 00000000 [ 25.251954] 1a40 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 [ 25.260247] 1a60 b40d5f5c 00000005 39b9fd7b 00000000 01d8655b 000002f5 00004e3c 00000000 [ 25.268539] 1a80 00000288 00000000 2f819847 00000000 0000404c 00000000 00004e3c 00000000 [ 25.276832] 1aa0 00000000 00000000 00000000 00000000 0000003c 00000000 fffef2ea 00000000 [ 25.285124] 1ac0 00000000 00000000 3df78200 ffffffc0 00000001 00000000 3666d3d8 ffffffc0 [ 25.293420] [ 25.293420] X16: 0xffffffc000217fc8: [ 25.298520] 7fc8 9272c401 17ffffef f9401420 52800021 94000d2e 17fffff4 91004297 f9400e81 [ 25.306812] 7fe8 2a1603e2 aa1703e0 940110b5 52800005 d2800004 52800023 aa1703e2 2a1603e1 [ 25.315105] 8008 aa1503e0 94010fb3 17ffffd8 33103c76 17ffffd4 928001b3 17ffffe3 f9401420 [ 25.323398] 8028 52800022 52800021 94000d28 17ffffbf 92800113 17ffffdc 928002b3 17ffffda [ 25.331690] 8048 a9bb7bfd 910003fd a90153f3 f90013f5 aa0003f3 aa1e03e0 f9001ba1 f9001fa2 [ 25.339983] 8068 d503201f 2a1303e0 94007739 f27ef414 aa0003f3 540003a0 910143a3 f9403a84 [ 25.348276] 8088 f9401fa2 aa1403e0 f9401ba1 f81f8c64 97fffea5 aa0003f5 b7f80075 f94027a0 [ 25.356569] 80a8 f9003a80 370800f3 37000133 aa1503e0 f94013f5 a94153f3 a8c57bfd d65f03c0 [ 25.364864] [ 25.364864] X19: 0xffffffc01854e070: [ 25.369964] e070 00000000 00000000 00000000 00000000 00000000 00000000 184b8000 ffffffc0 [ 25.378257] e090 00000002 00004040 00000000 00000000 00000000 00000000 00000000 00000008 [ 25.386550] e0b0 fffef292 00000000 35156f00 ffffffc0 00000004 00000001 00000078 00000078 [ 25.394843] e0d0 00000078 00000000 00be1588 ffffffc0 00000400 00000000 00400000 00000000 [ 25.403135] e0f0 184bce71 ffffffc0 00000000 00000000 00000000 00000000 184bc189 ffffffc0 [ 25.411429] e110 00000000 00000000 00000000 00000000 1854e120 ffffffc0 1854e120 ffffffc0 [ 25.419722] e130 00000001 00000000 00000000 00000000 002abd5e 00000000 068924ef 00000000 [ 25.428014] e150 002a82fa 00000000 00000005 00000000 b3f3976c 00000005 04b538fd 00000000 [ 25.436308] [ 25.436308] X20: 0xffffffc01694f358: [ 25.441408] f358 00000000 00000000 00000000 00000000 00000000 00000000 00000005 00000000 [ 25.449700] f378 00000003 00000000 00000001 00000000 00000003 00000000 00000002 00000000 [ 25.457993] f398 00000001 00000000 00000003 00000000 00000000 00000000 00000000 00000000 [ 25.466285] f3b8 00000001 00000000 367a0a00 ffffffc0 365f1a00 ffffffc0 00000000 00000000 [ 25.474577] f3d8 b40d5f5c 00000005 01ba1ce5 00000000 00209a2d 00000292 00000253 00000000 [ 25.482870] f3f8 0000002c 00000000 1694f400 ffffffc0 1694f400 ffffffc0 00000000 00000000 [ 25.491163] f418 00000000 00000000 00000019 00000000 00000000 00000000 00000000 00000000 [ 25.499455] f438 3df78368 ffffffc0 00000000 00000000 3679f400 ffffffc0 1694f450 ffffffc0 [ 25.507749] [ 25.507749] X22: 0xffffffc017d6ff80: [ 25.512850] ff80 07763000 ffffff80 07765000 ffffff80 00000002 00000000 17d6ff98 ffffffc0 [ 25.521144] ffa0 36e1db98 ffffffc0 37563718 ffffffc0 17d6ff30 ffffffc0 00000200 dead0000 [ 25.529437] ffc0 17d6ff40 ffffffc0 36e1dcc0 ffffffc0 00000000 00000000 17d6ff58 ffffffc0 [ 25.537731] ffe0 00000058 00000000 00000000 00000000 00000000 00000000 00000000 00000000 [ 25.546024] 0000 00000002 00000000 ffffffff ffffffff 17008080 ffffffc0 00000103 00000006 [ 25.554317] 0020 57ac6e9d 00000000 00000000 00000000 00000000 00000000 00000000 00000000 [ 25.562609] 0040 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 [ 25.570903] 0060 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 [ 25.579196] [ 25.579196] X24: 0xffffffc0365f1980: [ 25.584297] 1980 00000000 00000000 00000000 00000000 00000000 00000000 376d3ac0 ffffffc0 [ 25.592590] 19a0 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 [ 25.600881] 19c0 00000000 00000000 2cf4d220 ffffffc0 00000000 00000000 365f19d8 ffffffc0 [ 25.609173] 19e0 365f19d8 ffffffc0 365f19e8 ffffffc0 365f19e8 ffffffc0 2cfe84b0 ffffffc0 [ 25.617465] 1a00 00005000 00000000 00000000 00000000 00000014 00000014 195a1086 00000000 [ 25.625758] 1a20 06bb45fa 00000000 1854edf0 ffffffc0 1854e0f0 ffffffc0 00000000 00000000 [ 25.634051] 1a40 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 [ 25.642343] 1a60 b40d5f5c 00000005 39b9fd7b 00000000 01d8655b 000002f5 00004e3c 00000000 [ 25.650637] [ 25.650637] X27: 0xffffffc0365f1980: [ 25.655738] 1980 00000000 00000000 00000000 00000000 00000000 00000000 376d3ac0 ffffffc0 [ 25.664030] 19a0 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 [ 25.672321] 19c0 00000000 00000000 2cf4d220 ffffffc0 00000000 00000000 365f19d8 ffffffc0 [ 25.680613] 19e0 365f19d8 ffffffc0 365f19e8 ffffffc0 365f19e8 ffffffc0 2cfe84b0 ffffffc0 [ 25.688907] 1a00 00005000 00000000 00000000 00000000 00000014 00000014 195a1086 00000000 [ 25.697199] 1a20 06bb45fa 00000000 1854edf0 ffffffc0 1854e0f0 ffffffc0 00000000 00000000 [ 25.705493] 1a40 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 [ 25.713786] 1a60 b40d5f5c 00000005 39b9fd7b 00000000 01d8655b 000002f5 00004e3c 00000000 [ 25.722079] [ 25.722079] X28: 0xffffffc01694f1e0: [ 25.727180] f1e0 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 [ 25.735473] f200 00000000 00000000 16934000 ffffffc0 00000002 00004040 00000000 00000000 [ 25.743766] f220 00000000 00000000 00000000 00000028 fffef292 00000000 16b6b280 ffffffc0 [ 25.752059] f240 00000004 00000002 00000078 00000078 00000078 00000000 00be1588 ffffffc0 [ 25.760351] f260 00000400 00000000 00400000 00000000 16b68571 ffffffc0 00000000 00000000 [ 25.768643] f280 00000000 00000000 18796f09 ffffffc0 00000000 00000000 00000000 00000000 [ 25.776935] f2a0 1694f2a0 ffffffc0 1694f2a0 ffffffc0 00000000 00000000 b404cf96 00000005 [ 25.785228] f2c0 0033a981 00000000 ffe60568 ffffffff 0021de73 00000000 00000002 00000000 [ 25.793521] [ 25.793521] X29: 0xffffffc017d73860: [ 25.798622] 3860 1694f3d8 ffffffc0 00000000 00000000 17d70000 ffffffc0 00000007 00000000 [ 25.806914] 3880 365f1a00 ffffffc0 313bb52c 00000000 39b9fd7b 00000000 365f1a00 ffffffc0 [ 25.815207] 38a0 1694f260 ffffffc0 17d738e0 ffffffc0 000f6f60 ffffffc0 17d738e0 ffffffc0 [ 25.823500] 38c0 004c4550 ffffffc0 600001c5 00000000 00000000 00000000 1694f260 ffffffc0 [ 25.831792] 38e0 17d73990 ffffffc0 000eaed4 ffffffc0 3df78200 ffffffc0 1694f200 ffffffc0 [ 25.840084] 3900 00000002 00000000 00000140 00000000 17d73b10 ffffffc0 01072000 ffffffc0 [ 25.848376] 3920 00000001 00000000 01071130 ffffffc0 1694f200 ffffffc0 1694f288 ffffffc0 [ 25.856668] 3940 17d73950 00000000 3df78200 ffffffc0 00be1558 ffffffc0 00000400 00000000 [ 25.864960] [ 25.866462] Process hackbench (pid: 3028, stack limit = 0xffffffc017d70020) [ 25.873496] Stack: (0xffffffc017d738e0 to 0xffffffc017d74000) [ 25.879302] 38e0: ffffffc017d73990 ffffffc0000eaed4 ffffffc03df78200 ffffffc01694f200 [ 25.887214] 3900: 0000000000000002 0000000000000140 ffffffc017d73b10 ffffffc001072000 [ 25.895126] 3920: 0000000000000001 ffffffc001071130 ffffffc01694f200 ffffffc01694f288 [ 25.903038] 3940: 0000000017d73950 ffffffc03df78200 ffffffc000be1558 0000000000000400 [ 25.910949] 3960: 0000000000000400 ffffffc0365f1a60 0000000000000001 0000000000000007 [ 25.918861] 3980: 0000000000000400 ffffffc000000000 ffffffc017d739c0 ffffffc0000f4088 [ 25.926773] 39a0: ffffffc017d73ab0 ffffffc0000f40ec ffffffc000000000 ffffffc01694f200 [ 25.934685] 39c0: ffffffc017d739f0 ffffffc0000ff198 ffffffc018796f08 ffffffc03df78200 [ 25.942598] 39e0: 0000000000000002 0000000000000140 ffffffc017d73b20 ffffffc0000ff8cc [ 25.950510] 3a00: 00000000ffff2d82 ffffffc00106e000 0000000000000020 0000000000000001 [ 25.958421] 3a20: 0000000000000000 0000000000000000 ffffffc03df96200 0000000000000006 [ 25.966333] 3a40: ffffffc03795a800 0000000000009e49 ffffffc017d73bac ffffffc03df90a78 [ 25.974245] 3a60: ffffffc001051200 ffffffc03795b800 ffffffc000000001 ffffffc0000f6208 [ 25.982157] 3a80: ffffffc03795a804 ffffffc03795a800 ffffffc001051200 ffffffc001051200 [ 25.990068] 3aa0: 0000000000000006 ffffffc0011960a9 ffffffc03795a800 ffffffc03df78200 [ 25.997980] 3ac0: 0000000600000004 ffffffc03df96200 ffffffc037956720 0000000100000000 [ 26.005892] 3ae0: 000000000000007f 0000000000000017 ffffffc03df90a78 0000000200000000 [ 26.013804] 3b00: 0000001700000020 0000000300000002 ffffffc017344520 ffffffc017344520 [ 26.021715] 3b20: ffffffc017d73bb0 ffffffc0000ffbcc 00000000fffef2ea 0000000000000006 [ 26.029627] 3b40: ffffffc03df96200 0000000000000007 ffffffc017d70000 ffffffc001072000 [ 26.037539] 3b60: ffffffc001051200 ffffffc00106e000 ffffffc000e72000 ffffffc017d73c30 [ 26.045451] 3b80: 0000000000000007 0000000000000006 ffffffc0011b4b40 0000000000000007 [ 26.053363] 3ba0: ffffffc017d73bb0 00000001000ffa44 ffffffc017d73c30 ffffffc0000c3e1c [ 26.061274] 3bc0: 0000000000000007 0000000000000006 ffffffc00106e238 0000000000000007 [ 26.069186] 3be0: ffffffc017d70000 0000000000000020 0000000000000101 ffffffc00106e000 [ 26.077098] 3c00: ffffffc000e72000 ffffffc017d73c30 ffffffc00106e238 0000000000000001 [ 26.085009] 3c20: ffffffc017d73c30 ffffffc000000001 ffffffc017d73cc0 ffffffc0000c4398 [ 26.092922] 3c40: ffffffc00104e000 0000000000000000 ffffffc000f09000 ffffffc000f4a000 [ 26.100834] 3c60: 0000000000000000 0000000000000001 ffffffc005f32000 000000000000003f [ 26.108746] 3c80: ffffffc000bd7000 ffffffc017d70000 ffffffc00104e000 0000404000000000 [ 26.116657] 3ca0: 00000000fffef2eb 0000000a00000001 ffffffc00104ba48 ffffffc000e72a58 [ 26.124569] 3cc0: ffffffc017d73cd0 ffffffc0001195d0 ffffffc017d73d30 ffffffc000082524 [ 26.132481] 3ce0: ffffff800000400c ffffffc017d73d70 ffffffc001074000 ffffff8000004010 [ 26.140393] 3d00: ffffff8000005000 0000000000000015 000000000000011d ffffffc00106f000 [ 26.148305] 3d20: ffffffc017d73d70 0000001e0008559c ffffffc017d73e90 ffffffc0000855ac [ 26.156217] 3d40: ffffffc017008a00 ffffffc017d73ed0 ffffffc017d73e90 ffffffc0000867cc [ 26.164128] 3d60: 0000000080000145 000000000000003f ffffffc017008a00 ffffffc017d70000 [ 26.172039] 3d80: 0000000000000000 0000000000000003 0000000000000008 0000000000000000 [ 26.179951] 3da0: 0000007ffffff774 2d2d2d2d2d2d2d2d 2d2d2d2d2d2d2d2d 2d2d2d2d2d2d2d2d [ 26.187863] 3dc0: 2d2d2d2d2d2d2d2d 2d2d2d2d2d2d2d2d 2d2d2d2d2d2d2d2d 2d2d2d2d2d2d2d2d [ 26.195775] 3de0: 2d2d2d2d2d2d2d2d 00000000004a49a8 ffffffc000218048 0000000000000001 [ 26.203687] 3e00: 0000000000000000 ffffffc017008a00 ffffffc017d73ed0 ffffffffffffffff [ 26.211599] 3e20: 000000000040626c 0000000060000000 0000000000000015 000000000000011d [ 26.219510] 3e40: 000000000000003f ffffffc000bd7000 ffffffc017d70000 ffffffc017d73e90 [ 26.227422] 3e60: ffffffc000086444 ffffffc017d73e90 ffffffc0000867cc 0000000080000145 [ 26.235334] 3e80: 0000000000000008 ffffffc017d73ed0 ffffffc017d73eb0 ffffffc00008a310 [ 26.243245] 3ea0: 0000000000000008 0000000d00000002 0000007ffffff780 ffffffc000085ba8 [ 26.251157] 3ec0: 0000000000000000 00000000004abb90 0000000000000064 0000007ffffff710 [ 26.259069] 3ee0: 0000000000000064 0000000000000000 0000000000000000 0000000000000001 [ 26.266980] 3f00: 0000007ffffff770 0000000000000000 000000000000003f 0000000000000000 [ 26.274891] 3f20: 0000000000000000 0000000000000000 0000000000000000 0000007ffffff770 [ 26.282803] 3f40: 0000000000402044 00000000004a49a8 0000000000000000 0000000000000001 [ 26.290714] 3f60: 0000000000000000 0000000000000000 00000000004abb90 0000007ffffff710 [ 26.298627] 3f80: 000000000049e010 0000000000000266 0000007ffffff780 0000000000000118 [ 26.306538] 3fa0: 000000000000000a 0000000000000009 00000000000008c0 0000007ffffff780 [ 26.314450] 3fc0: 0000000000402334 0000007ffffff710 000000000040626c 0000000060000000 [ 26.322361] 3fe0: 000000000000000c 000000000000003f 0000000000000000 0000000000000000 [ 26.330270] Call trace: [ 26.332739] [<ffffffc0004c4550>] rb_erase+0x1a4/0x394 [ 26.337844] [<ffffffc0000eaed4>] deactivate_task+0x98/0xbc [ 26.343386] [<ffffffc0000f4088>] detach_task+0x30/0xc8 [ 26.348577] [<ffffffc0000ff198>] load_balance+0x3cc/0x994 [ 26.354031] [<ffffffc0000ff8cc>] rebalance_domains+0x16c/0x2ac [ 26.359924] [<ffffffc0000ffbcc>] run_rebalance_domains+0x1c0/0x1e8 [ 26.366169] [<ffffffc0000c3e1c>] __do_softirq+0x160/0x3ac [ 26.371622] [<ffffffc0000c4398>] irq_exit+0xb0/0xdc [ 26.376551] [<ffffffc0001195d0>] __handle_domain_irq+0x94/0xf8 [ 26.382444] [<ffffffc000082524>] gic_handle_irq+0x5c/0xa8 [ 26.387897] Exception stack(0xffffffc017d73d40 to 0xffffffc017d73e60) [ 26.394404] 3d40: ffffffc017008a00 ffffffc017d73ed0 ffffffc017d73e90 ffffffc0000867cc [ 26.402316] 3d60: 0000000080000145 000000000000003f ffffffc017008a00 ffffffc017d70000 [ 26.410227] 3d80: 0000000000000000 0000000000000003 0000000000000008 0000000000000000 [ 26.418139] 3da0: 0000007ffffff774 2d2d2d2d2d2d2d2d 2d2d2d2d2d2d2d2d 2d2d2d2d2d2d2d2d [ 26.426051] 3dc0: 2d2d2d2d2d2d2d2d 2d2d2d2d2d2d2d2d 2d2d2d2d2d2d2d2d 2d2d2d2d2d2d2d2d [ 26.433963] 3de0: 2d2d2d2d2d2d2d2d 00000000004a49a8 ffffffc000218048 0000000000000001 [ 26.441875] 3e00: 0000000000000000 ffffffc017008a00 ffffffc017d73ed0 ffffffffffffffff [ 26.449786] 3e20: 000000000040626c 0000000060000000 0000000000000015 000000000000011d [ 26.457698] 3e40: 000000000000003f ffffffc000bd7000 ffffffc017d70000 ffffffc017d73e90 [ 26.465611] [<ffffffc0000855ac>] el1_irq+0x6c/0xe0 [ 26.470451] [<ffffffc00008a310>] do_notify_resume+0x2c/0x84 [ 26.476080] [<ffffffc000085ba8>] work_pending+0x1c/0x20 [ 26.481359] Code: f9400404 b2400043 f9000844 f9000402 (f9000083) [ 26.487545] ---[ end trace a63b1ba0d64611aa ]--- [ 26.494934] Kernel panic - not syncing: Fatal exception in interrupt [ 27.334687] SMP: failed to stop secondary CPUs [ 27.351435] Rebooting in 5 seconds.. [ 33.188202] SMP: failed to stop secondary CPUs
eas-dev mailing list eas-dev@lists.linaro.org https://lists.linaro.org/mailman/listinfo/eas-dev
On Tue, Nov 15, 2016 at 03:22:59PM +0000, Patrick Bellasi wrote:
On 15-Nov 22:05, Leo Yan wrote:
But this code is delibrately written for WALT to update souce rq and destination rq statistics for workload. So currently I can simply revert double_lock_balance()/double_unlock_balance() for only using PELT signals, but for WALT I want to get some suggestion for the fixing, if we confirm this is a potential issue, this issue should exist both on Android common kernel 3.18 and 4.4.
AFAIK, in the (simplified) version of WALT posted on LKML before LPC [2] Vikram got ride of all the double loking. If the problem you reported is verified, than we should probably try to update AOSP WALT using the same locking schema used by the LKML posting.
[1] http://www2.comp.ufscar.br/lxr/source/Documentation/RCU/RTFP.txt#L176 [2] https://lkml.org/lkml/2016/10/28/84
Cheers Patrick
/*
- detach_task() -- detach the task for the migration specified in env
*/ static void detach_task(struct task_struct *p, struct lb_env *env) { lockdep_assert_held(&env->src_rq->lock);
deactivate_task(env->src_rq, p, 0); p->on_rq = TASK_ON_RQ_MIGRATING; double_lock_balance(env->src_rq, env->dst_rq); set_task_cpu(p, env->dst_cpu); double_unlock_balance(env->src_rq, env->dst_rq);}
I'm a bit worried that this unlocking business as part of the double-locking in detach_task() is not safe.
If the code looks anything like mainline in detach_tasks() (notice the s), I don't think it is safe.
Morten IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you.
Hello,
On 11/15/2016 08:55 AM, Morten Rasmussen wrote:
On Tue, Nov 15, 2016 at 03:22:59PM +0000, Patrick Bellasi wrote:
On 15-Nov 22:05, Leo Yan wrote:
But this code is delibrately written for WALT to update souce rq and destination rq statistics for workload. So currently I can simply revert double_lock_balance()/double_unlock_balance() for only using PELT signals, but for WALT I want to get some suggestion for the fixing, if we confirm this is a potential issue, this issue should exist both on Android common kernel 3.18 and 4.4.
AFAIK, in the (simplified) version of WALT posted on LKML before LPC [2] Vikram got ride of all the double loking. If the problem you reported is verified, than we should probably try to update AOSP WALT using the same locking schema used by the LKML posting.
[1] http://www2.comp.ufscar.br/lxr/source/Documentation/RCU/RTFP.txt#L176 [2] https://lkml.org/lkml/2016/10/28/84
Cheers Patrick
/*
- detach_task() -- detach the task for the migration specified in env
*/ static void detach_task(struct task_struct *p, struct lb_env *env) { lockdep_assert_held(&env->src_rq->lock);
deactivate_task(env->src_rq, p, 0); p->on_rq = TASK_ON_RQ_MIGRATING; double_lock_balance(env->src_rq, env->dst_rq); set_task_cpu(p, env->dst_cpu); double_unlock_balance(env->src_rq, env->dst_rq);}
I'm a bit worried that this unlocking business as part of the double-locking in detach_task() is not safe.
If the code looks anything like mainline in detach_tasks() (notice the s), I don't think it is safe.
I do agree that the double_lock_balance is fragile in that new code - such as Leo's - may (rightfully) never consider that the rq lock is being dropped. The LKML implementation that Patrick pointed out does indeed eliminate double locking and should be quite easy to port to WALT on android-common/LSK. I don't think there's a good intermediate solution otherwise (sorry Leo!). We should move over to that implementation wherever WALT is being used with EAS for upcoming development to at the very least not have to think about the lock being dropped.
For 3.18/4.4, the code paths involved were audited when the double-locking was added back when we first upgraded to 3.18 in 2014, and given the sheer number of hours of commercial testing, I daresay that it has been safe so far to drop the rq lock from a stability perspective with the HMP scheduler and with the EAS scheduler (I think because the lock is dropped after the task is dequeued in all cases), neither of which mess with these LB code paths to an extent that would mask a potential problem. So android/common kernel-3.18/kernel-4.4 should be safe for now.
Morten IMPORTANT NOTICE: The contents of this email and any attachments are confidential and may also be privileged. If you are not the intended recipient, please notify the sender immediately and do not disclose the contents to any other person, use it for any purpose, or store or copy the information in any medium. Thank you. _______________________________________________ eas-dev mailing list eas-dev@lists.linaro.org https://lists.linaro.org/mailman/listinfo/eas-dev
Hi Vikram,
On Tue, Nov 15, 2016 at 03:18:39PM -0800, Vikram Mulukutla wrote:
[...]
/*
- detach_task() -- detach the task for the migration specified in env
*/ static void detach_task(struct task_struct *p, struct lb_env *env) { lockdep_assert_held(&env->src_rq->lock);
deactivate_task(env->src_rq, p, 0); p->on_rq = TASK_ON_RQ_MIGRATING; double_lock_balance(env->src_rq, env->dst_rq); set_task_cpu(p, env->dst_cpu); double_unlock_balance(env->src_rq, env->dst_rq);}
I'm a bit worried that this unlocking business as part of the double-locking in detach_task() is not safe.
If the code looks anything like mainline in detach_tasks() (notice the s), I don't think it is safe.
I do agree that the double_lock_balance is fragile in that new code
- such as Leo's - may (rightfully) never consider that the rq lock
is being dropped. The LKML implementation that Patrick pointed out does indeed eliminate double locking and should be quite easy to port to WALT on android-common/LSK. I don't think there's a good intermediate solution otherwise (sorry Leo!). We should move over to that implementation wherever WALT is being used with EAS for upcoming development to at the very least not have to think about the lock being dropped.
Thanks for confirmation. I will try to port your latest patches for this.
For 3.18/4.4, the code paths involved were audited when the double-locking was added back when we first upgraded to 3.18 in 2014, and given the sheer number of hours of commercial testing, I daresay that it has been safe so far to drop the rq lock from a stability perspective with the HMP scheduler and with the EAS scheduler (I think because the lock is dropped after the task is dequeued in all cases), neither of which mess with these LB code paths to an extent that would mask a potential problem. So android/common kernel-3.18/kernel-4.4 should be safe for now.
Yeah. I reviewed rq::cfs_tasks and rb tree for vruntime, it's true neither of them has the situation to dereference one same pointer variable before and after detach_task(); so they should be safe.
Thanks, Leo Yan
Hi Patrick,
On Tue, Nov 15, 2016 at 03:22:59PM +0000, Patrick Bellasi wrote:
[...]
I'm wondering if your rb_tree usage can be extended to be lockless. This should be achievable by properly using reference couting for each node, thus marking a node as "in use" right after your rb_bext call, or better using RCU to protect the reader side.
This last option would be ultimately a better and more generic solution but it can became quite complex. You should still be able to find some exaple of RCU-protected rb-trees... in the past this technique has been already used for example by Nick Piggin in it's fully lockless dentry search [1] back in the 2011.
Thanks a lot for sharing related info. For rb-tree usage, basically I think it doesn't introduce any extra locking but completely rely on rq lock. If rb-tree introduce RCU for lockless looks like this will let things more complex, because we finally will get rq locking and rcu mixed.
Please let me know if I miss anything?
[...]
Thanks, Leo Yan
-
Leo Yan -
Morten Rasmussen -
Patrick Bellasi -
Vikram Mulukutla