1*36929ebdSEmil Tsalapatis /* 2*36929ebdSEmil Tsalapatis * SPDX-License-Identifier: GPL-2.0 3*36929ebdSEmil Tsalapatis * Copyright (c) 2025 Meta Platforms, Inc. and affiliates. 4*36929ebdSEmil Tsalapatis * Copyright (c) 2025 Tejun Heo <tj@kernel.org> 5*36929ebdSEmil Tsalapatis * Copyright (c) 2025 Emil Tsalapatis <etsal@meta.com> 6*36929ebdSEmil Tsalapatis */ 7*36929ebdSEmil Tsalapatis #pragma once 8*36929ebdSEmil Tsalapatis 9*36929ebdSEmil Tsalapatis #ifndef __BPF__ 10*36929ebdSEmil Tsalapatis #define __arena 11*36929ebdSEmil Tsalapatis #endif /* __BPF__ */ 12*36929ebdSEmil Tsalapatis 13*36929ebdSEmil Tsalapatis struct scx_alloc_stats { 14*36929ebdSEmil Tsalapatis __u64 chunk_allocs; 15*36929ebdSEmil Tsalapatis __u64 data_allocs; 16*36929ebdSEmil Tsalapatis __u64 alloc_ops; 17*36929ebdSEmil Tsalapatis __u64 free_ops; 18*36929ebdSEmil Tsalapatis __u64 active_allocs; 19*36929ebdSEmil Tsalapatis __u64 arena_pages_used; 20*36929ebdSEmil Tsalapatis }; 21*36929ebdSEmil Tsalapatis 22*36929ebdSEmil Tsalapatis struct sdt_pool { 23*36929ebdSEmil Tsalapatis void __arena *slab; 24*36929ebdSEmil Tsalapatis __u64 elem_size; 25*36929ebdSEmil Tsalapatis __u64 max_elems; 26*36929ebdSEmil Tsalapatis __u64 idx; 27*36929ebdSEmil Tsalapatis }; 28*36929ebdSEmil Tsalapatis 29*36929ebdSEmil Tsalapatis #ifndef div_round_up 30*36929ebdSEmil Tsalapatis #define div_round_up(a, b) (((a) + (b) - 1) / (b)) 31*36929ebdSEmil Tsalapatis #endif 32*36929ebdSEmil Tsalapatis 33*36929ebdSEmil Tsalapatis #ifndef round_up 34*36929ebdSEmil Tsalapatis #define round_up(a, b) (div_round_up((a), (b)) * (b)) 35*36929ebdSEmil Tsalapatis #endif 36*36929ebdSEmil Tsalapatis 37*36929ebdSEmil Tsalapatis typedef struct sdt_desc __arena sdt_desc_t; 38*36929ebdSEmil Tsalapatis 39*36929ebdSEmil Tsalapatis enum sdt_consts { 40*36929ebdSEmil Tsalapatis SDT_TASK_ENTS_PER_PAGE_SHIFT = 9, 41*36929ebdSEmil Tsalapatis SDT_TASK_LEVELS = 3, 42*36929ebdSEmil Tsalapatis SDT_TASK_ENTS_PER_CHUNK = 1 << SDT_TASK_ENTS_PER_PAGE_SHIFT, 43*36929ebdSEmil Tsalapatis SDT_TASK_CHUNK_BITMAP_U64S = div_round_up(SDT_TASK_ENTS_PER_CHUNK, 64), 44*36929ebdSEmil Tsalapatis SDT_TASK_MIN_ELEM_PER_ALLOC = 8, 45*36929ebdSEmil Tsalapatis }; 46*36929ebdSEmil Tsalapatis 47*36929ebdSEmil Tsalapatis union sdt_id { 48*36929ebdSEmil Tsalapatis __s64 val; 49*36929ebdSEmil Tsalapatis struct { 50*36929ebdSEmil Tsalapatis __s32 idx; /* index in the radix tree */ 51*36929ebdSEmil Tsalapatis __s32 genn; /* ++'d on recycle so that it forms unique'ish 64bit ID */ 52*36929ebdSEmil Tsalapatis }; 53*36929ebdSEmil Tsalapatis }; 54*36929ebdSEmil Tsalapatis 55*36929ebdSEmil Tsalapatis struct sdt_chunk; 56*36929ebdSEmil Tsalapatis 57*36929ebdSEmil Tsalapatis /* 58*36929ebdSEmil Tsalapatis * Each index page is described by the following descriptor which carries the 59*36929ebdSEmil Tsalapatis * bitmap. This way the actual index can host power-of-two numbers of entries 60*36929ebdSEmil Tsalapatis * which makes indexing cheaper. 61*36929ebdSEmil Tsalapatis */ 62*36929ebdSEmil Tsalapatis struct sdt_desc { 63*36929ebdSEmil Tsalapatis __u64 allocated[SDT_TASK_CHUNK_BITMAP_U64S]; 64*36929ebdSEmil Tsalapatis __u64 nr_free; 65*36929ebdSEmil Tsalapatis struct sdt_chunk __arena *chunk; 66*36929ebdSEmil Tsalapatis }; 67*36929ebdSEmil Tsalapatis 68*36929ebdSEmil Tsalapatis /* 69*36929ebdSEmil Tsalapatis * Leaf node containing per-task data. 70*36929ebdSEmil Tsalapatis */ 71*36929ebdSEmil Tsalapatis struct sdt_data { 72*36929ebdSEmil Tsalapatis union sdt_id tid; 73*36929ebdSEmil Tsalapatis __u64 payload[]; 74*36929ebdSEmil Tsalapatis }; 75*36929ebdSEmil Tsalapatis 76*36929ebdSEmil Tsalapatis /* 77*36929ebdSEmil Tsalapatis * Intermediate node pointing to another intermediate node or leaf node. 78*36929ebdSEmil Tsalapatis */ 79*36929ebdSEmil Tsalapatis struct sdt_chunk { 80*36929ebdSEmil Tsalapatis union { 81*36929ebdSEmil Tsalapatis sdt_desc_t * descs[SDT_TASK_ENTS_PER_CHUNK]; 82*36929ebdSEmil Tsalapatis struct sdt_data __arena *data[SDT_TASK_ENTS_PER_CHUNK]; 83*36929ebdSEmil Tsalapatis }; 84*36929ebdSEmil Tsalapatis }; 85*36929ebdSEmil Tsalapatis 86*36929ebdSEmil Tsalapatis struct scx_allocator { 87*36929ebdSEmil Tsalapatis struct sdt_pool pool; 88*36929ebdSEmil Tsalapatis sdt_desc_t *root; 89*36929ebdSEmil Tsalapatis }; 90*36929ebdSEmil Tsalapatis 91*36929ebdSEmil Tsalapatis struct scx_stats { 92*36929ebdSEmil Tsalapatis int seq; 93*36929ebdSEmil Tsalapatis pid_t pid; 94*36929ebdSEmil Tsalapatis __u64 enqueue; 95*36929ebdSEmil Tsalapatis __u64 exit; 96*36929ebdSEmil Tsalapatis __u64 init; 97*36929ebdSEmil Tsalapatis __u64 select_busy_cpu; 98*36929ebdSEmil Tsalapatis __u64 select_idle_cpu; 99*36929ebdSEmil Tsalapatis }; 100*36929ebdSEmil Tsalapatis 101*36929ebdSEmil Tsalapatis #ifdef __BPF__ 102*36929ebdSEmil Tsalapatis 103*36929ebdSEmil Tsalapatis void __arena *scx_task_data(struct task_struct *p); 104*36929ebdSEmil Tsalapatis int scx_task_init(__u64 data_size); 105*36929ebdSEmil Tsalapatis void __arena *scx_task_alloc(struct task_struct *p); 106*36929ebdSEmil Tsalapatis void scx_task_free(struct task_struct *p); 107*36929ebdSEmil Tsalapatis void scx_arena_subprog_init(void); 108*36929ebdSEmil Tsalapatis 109*36929ebdSEmil Tsalapatis int scx_alloc_init(struct scx_allocator *alloc, __u64 data_size); 110*36929ebdSEmil Tsalapatis u64 scx_alloc_internal(struct scx_allocator *alloc); 111*36929ebdSEmil Tsalapatis int scx_alloc_free_idx(struct scx_allocator *alloc, __u64 idx); 112*36929ebdSEmil Tsalapatis 113*36929ebdSEmil Tsalapatis #endif /* __BPF__ */ 114