Something went wrong. Try again.
Linux kernel mirror (for testing) git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Something went wrong. Try again.
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536// SPDX-License-Identifier: GPL-2.0-only/* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com * Copyright (c) 2016 Facebook */#include <linux/bpf.h>#include <linux/btf.h>#include <linux/jhash.h>#include <linux/filter.h>#include <linux/rculist_nulls.h>#include <linux/rcupdate_wait.h>#include <linux/random.h>#include <linux/rhashtable.h>#include <uapi/linux/btf.h>#include <linux/rcupdate_trace.h>#include <linux/btf_ids.h>#include "percpu_freelist.h"#include "bpf_lru_list.h"#include "map_in_map.h"#include <linux/bpf_mem_alloc.h>#include <asm/rqspinlock.h>
#define HTAB_CREATE_FLAG_MASK \ (BPF_F_NO_PREALLOC | BPF_F_NO_COMMON_LRU | BPF_F_NUMA_NODE | \ BPF_F_ACCESS_MASK | BPF_F_ZERO_SEED)
#define BATCH_OPS(_name) \ .map_lookup_batch = \ _name##_map_lookup_batch, \ .map_lookup_and_delete_batch = \ _name##_map_lookup_and_delete_batch, \ .map_update_batch = \ generic_map_update_batch, \ .map_delete_batch = \ generic_map_delete_batch
/* * The bucket lock has two protection scopes: * * 1) Serializing concurrent operations from BPF programs on different * CPUs * * 2) Serializing concurrent operations from BPF programs and sys_bpf() * * BPF programs can execute in any context including perf, kprobes and * tracing. As there are almost no limits where perf, kprobes and tracing * can be invoked from the lock operations need to be protected against * deadlocks. Deadlocks can be caused by recursion and by an invocation in * the lock held section when functions which acquire this lock are invoked * from sys_bpf(). BPF recursion is prevented by incrementing the per CPU * variable bpf_prog_active, which prevents BPF programs attached to perf * events, kprobes and tracing to be invoked before the prior invocation * from one of these contexts completed. sys_bpf() uses the same mechanism * by pinning the task to the current CPU and incrementing the recursion * protection across the map operation. * * This has subtle implications on PREEMPT_RT. PREEMPT_RT forbids certain * operations like memory allocations (even with GFP_ATOMIC) from atomic * contexts. This is required because even with GFP_ATOMIC the memory * allocator calls into code paths which acquire locks with long held lock * sections. To ensure the deterministic behaviour these locks are regular * spinlocks, which are converted to 'sleepable' spinlocks on RT. The only * true atomic contexts on an RT kernel are the low level hardware * handling, scheduling, low level interrupt handling, NMIs etc. None of * these contexts should ever do memory allocations. * * As regular device interrupt handlers and soft interrupts are forced into * thread context, the existing code which does * spin_lock*(); alloc(GFP_ATOMIC); spin_unlock*(); * just works. * * In theory the BPF locks could be converted to regular spinlocks as well, * but the bucket locks and percpu_freelist locks can be taken from * arbitrary contexts (perf, kprobes, tracepoints) which are required to be * atomic contexts even on RT. Before the introduction of bpf_mem_alloc, * it is only safe to use raw spinlock for preallocated hash map on a RT kernel, * because there is no memory allocation within the lock held sections. However * after hash map was fully converted to use bpf_mem_alloc, there will be * non-synchronous memory allocation for non-preallocated hash map, so it is * safe to always use raw spinlock for bucket lock. */struct bucket { struct hlist_nulls_head head; rqspinlock_t raw_lock;};
struct bpf_htab { struct bpf_map map; struct bpf_mem_alloc ma; struct bpf_mem_alloc pcpu_ma; struct bucket *buckets; void *elems; union { struct pcpu_freelist freelist; struct bpf_lru lru; }; struct htab_elem *__percpu *extra_elems; /* number of elements in non-preallocated hashtable are kept * in either pcount or count */ struct percpu_counter pcount; atomic_t count; bool use_percpu_counter; u32 n_buckets; /* number of hash buckets */ u32 elem_size; /* size of each element in bytes */ u32 hashrnd;};
/* each htab element is struct htab_elem + key + value */struct htab_elem { union { struct hlist_nulls_node hash_node; struct { void *padding; union { struct pcpu_freelist_node fnode; struct htab_elem *batch_flink; }; }; }; union { /* pointer to per-cpu pointer */ void *ptr_to_pptr; struct bpf_lru_node lru_node; }; u32 hash; char key[] __aligned(8);};
struct htab_btf_record { struct btf_record *record; u32 key_size;};
static inline bool htab_is_prealloc(const struct bpf_htab *htab){ return !(htab->map.map_flags & BPF_F_NO_PREALLOC);}
static void htab_init_buckets(struct bpf_htab *htab){ unsigned int i;
for (i = 0; i < htab->n_buckets; i++) { INIT_HLIST_NULLS_HEAD(&htab->buckets[i].head, i); raw_res_spin_lock_init(&htab->buckets[i].raw_lock); cond_resched(); }}
static inline int htab_lock_bucket(struct bucket *b, unsigned long *pflags){ unsigned long flags; int ret;
ret = raw_res_spin_lock_irqsave(&b->raw_lock, flags); if (ret) return ret; *pflags = flags; return 0;}
static inline void htab_unlock_bucket(struct bucket *b, unsigned long flags){ raw_res_spin_unlock_irqrestore(&b->raw_lock, flags);}
static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node);
static bool htab_is_lru(const struct bpf_htab *htab){ return htab->map.map_type == BPF_MAP_TYPE_LRU_HASH || htab->map.map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH;}
static bool htab_is_percpu(const struct bpf_htab *htab){ return htab->map.map_type == BPF_MAP_TYPE_PERCPU_HASH || htab->map.map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH;}
static inline bool is_fd_htab(const struct bpf_htab *htab){ return htab->map.map_type == BPF_MAP_TYPE_HASH_OF_MAPS;}
static inline void *htab_elem_value(struct htab_elem *l, u32 key_size){ return l->key + round_up(key_size, 8);}
static inline void htab_elem_set_ptr(struct htab_elem *l, u32 key_size, void __percpu *pptr){ *(void __percpu **)htab_elem_value(l, key_size) = pptr;}
static inline void __percpu *htab_elem_get_ptr(struct htab_elem *l, u32 key_size){ return *(void __percpu **)htab_elem_value(l, key_size);}
static void *fd_htab_map_get_ptr(const struct bpf_map *map, struct htab_elem *l){ return *(void **)htab_elem_value(l, map->key_size);}
static struct htab_elem *get_htab_elem(struct bpf_htab *htab, int i){ return (struct htab_elem *) (htab->elems + i * (u64)htab->elem_size);}
/* Both percpu and fd htab support in-place update, so no need for * extra elem. LRU itself can remove the least used element, so * there is no need for an extra elem during map_update. */static bool htab_has_extra_elems(struct bpf_htab *htab){ return !htab_is_percpu(htab) && !htab_is_lru(htab) && !is_fd_htab(htab);}
static void htab_free_prealloced_internal_structs(struct bpf_htab *htab){ u32 num_entries = htab->map.max_entries; int i;
if (htab_has_extra_elems(htab)) num_entries += num_possible_cpus();
for (i = 0; i < num_entries; i++) { struct htab_elem *elem;
elem = get_htab_elem(htab, i); bpf_map_free_internal_structs(&htab->map, htab_elem_value(elem, htab->map.key_size)); cond_resched(); }}
static void htab_free_prealloced_fields(struct bpf_htab *htab){ u32 num_entries = htab->map.max_entries; int i;
if (IS_ERR_OR_NULL(htab->map.record)) return; /* * Preallocated maps do not have a bpf_mem_alloc destructor, so fully * destroy every element, including the extra elements. */ if (htab_has_extra_elems(htab)) num_entries += num_possible_cpus(); for (i = 0; i < num_entries; i++) { struct htab_elem *elem;
elem = get_htab_elem(htab, i); if (htab_is_percpu(htab)) { void __percpu *pptr = htab_elem_get_ptr(elem, htab->map.key_size); int cpu;
for_each_possible_cpu(cpu) { bpf_obj_free_fields(htab->map.record, per_cpu_ptr(pptr, cpu)); cond_resched(); } } else { bpf_obj_free_fields(htab->map.record, htab_elem_value(elem, htab->map.key_size)); cond_resched(); } cond_resched(); }}
static void htab_free_elems(struct bpf_htab *htab){ int i;
if (!htab_is_percpu(htab)) goto free_elems;
for (i = 0; i < htab->map.max_entries; i++) { void __percpu *pptr;
pptr = htab_elem_get_ptr(get_htab_elem(htab, i), htab->map.key_size); free_percpu(pptr); cond_resched(); }free_elems: bpf_map_area_free(htab->elems);}
/* The LRU list has a lock (lru_lock). Each htab bucket has a lock * (bucket_lock). If both locks need to be acquired together, the lock * order is always lru_lock -> bucket_lock and this only happens in * bpf_lru_list.c logic. For example, certain code path of * bpf_lru_pop_free(), which is called by function prealloc_lru_pop(), * will acquire lru_lock first followed by acquiring bucket_lock. * * In hashtab.c, to avoid deadlock, lock acquisition of * bucket_lock followed by lru_lock is not allowed. In such cases, * bucket_lock needs to be released first before acquiring lru_lock. */static struct htab_elem *prealloc_lru_pop(struct bpf_htab *htab, void *key, u32 hash){ struct bpf_lru_node *node = bpf_lru_pop_free(&htab->lru, hash); struct htab_elem *l;
if (node) { bpf_map_inc_elem_count(&htab->map); l = container_of(node, struct htab_elem, lru_node); memcpy(l->key, key, htab->map.key_size); return l; }
return NULL;}
static int prealloc_init(struct bpf_htab *htab){ u32 num_entries = htab->map.max_entries; int err = -ENOMEM, i;
if (htab_has_extra_elems(htab)) num_entries += num_possible_cpus();
htab->elems = bpf_map_area_alloc((u64)htab->elem_size * num_entries, htab->map.numa_node); if (!htab->elems) return -ENOMEM;
if (!htab_is_percpu(htab)) goto skip_percpu_elems;
for (i = 0; i < num_entries; i++) { u32 size = round_up(htab->map.value_size, 8); void __percpu *pptr;
pptr = bpf_map_alloc_percpu(&htab->map, size, 8, GFP_USER | __GFP_NOWARN); if (!pptr) goto free_elems; htab_elem_set_ptr(get_htab_elem(htab, i), htab->map.key_size, pptr); cond_resched(); }
skip_percpu_elems: if (htab_is_lru(htab)) err = bpf_lru_init(&htab->lru, htab->map.map_flags & BPF_F_NO_COMMON_LRU, offsetof(struct htab_elem, hash) - offsetof(struct htab_elem, lru_node), htab_lru_map_delete_node, htab); else err = pcpu_freelist_init(&htab->freelist);
if (err) goto free_elems;
if (htab_is_lru(htab)) bpf_lru_populate(&htab->lru, htab->elems, offsetof(struct htab_elem, lru_node), htab->elem_size, num_entries); else pcpu_freelist_populate(&htab->freelist, htab->elems + offsetof(struct htab_elem, fnode), htab->elem_size, num_entries);
return 0;
free_elems: htab_free_elems(htab); return err;}
static void prealloc_destroy(struct bpf_htab *htab){ htab_free_elems(htab);
if (htab_is_lru(htab)) bpf_lru_destroy(&htab->lru); else pcpu_freelist_destroy(&htab->freelist);}
static int alloc_extra_elems(struct bpf_htab *htab){ struct htab_elem *__percpu *pptr, *l_new; struct pcpu_freelist_node *l; int cpu;
pptr = bpf_map_alloc_percpu(&htab->map, sizeof(struct htab_elem *), 8, GFP_USER | __GFP_NOWARN); if (!pptr) return -ENOMEM;
for_each_possible_cpu(cpu) { l = pcpu_freelist_pop(&htab->freelist); /* pop will succeed, since prealloc_init() * preallocated extra num_possible_cpus elements */ l_new = container_of(l, struct htab_elem, fnode); *per_cpu_ptr(pptr, cpu) = l_new; } htab->extra_elems = pptr; return 0;}
/* Called from syscall */static int htab_map_alloc_check(union bpf_attr *attr){ bool percpu = (attr->map_type == BPF_MAP_TYPE_PERCPU_HASH || attr->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH); bool lru = (attr->map_type == BPF_MAP_TYPE_LRU_HASH || attr->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH); /* percpu_lru means each cpu has its own LRU list. * it is different from BPF_MAP_TYPE_PERCPU_HASH where * the map's value itself is percpu. percpu_lru has * nothing to do with the map's value. */ bool percpu_lru = (attr->map_flags & BPF_F_NO_COMMON_LRU); bool prealloc = !(attr->map_flags & BPF_F_NO_PREALLOC); bool zero_seed = (attr->map_flags & BPF_F_ZERO_SEED); int numa_node = bpf_map_attr_numa_node(attr);
BUILD_BUG_ON(offsetof(struct htab_elem, fnode.next) != offsetof(struct htab_elem, hash_node.pprev));
if (zero_seed && !capable(CAP_SYS_ADMIN)) /* Guard against local DoS, and discourage production use. */ return -EPERM;
if (attr->map_flags & ~HTAB_CREATE_FLAG_MASK || !bpf_map_flags_access_ok(attr->map_flags)) return -EINVAL;
if (!lru && percpu_lru) return -EINVAL;
if (lru && !prealloc) return -ENOTSUPP;
if (numa_node != NUMA_NO_NODE && (percpu || percpu_lru)) return -EINVAL;
/* check sanity of attributes. * value_size == 0 may be allowed in the future to use map as a set */ if (attr->max_entries == 0 || attr->key_size == 0 || attr->value_size == 0) return -EINVAL;
if ((u64)attr->key_size + attr->value_size >= KMALLOC_MAX_SIZE - sizeof(struct htab_elem)) /* if key_size + value_size is bigger, the user space won't be * able to access the elements via bpf syscall. This check * also makes sure that the elem_size doesn't overflow and it's * kmalloc-able later in htab_map_update_elem() */ return -E2BIG; /* percpu map value size is bound by PCPU_MIN_UNIT_SIZE */ if (percpu && round_up(attr->value_size, 8) > PCPU_MIN_UNIT_SIZE) return -E2BIG;
return 0;}
static void htab_mem_dtor(void *obj, void *ctx){ struct htab_btf_record *hrec = ctx; struct htab_elem *elem = obj; void *map_value;
if (IS_ERR_OR_NULL(hrec->record)) return;
map_value = htab_elem_value(elem, hrec->key_size); bpf_obj_free_fields(hrec->record, map_value);}
static void htab_pcpu_mem_dtor(void *obj, void *ctx){ void __percpu *pptr = *(void __percpu **)obj; struct htab_btf_record *hrec = ctx; int cpu;
if (IS_ERR_OR_NULL(hrec->record)) return;
for_each_possible_cpu(cpu) bpf_obj_free_fields(hrec->record, per_cpu_ptr(pptr, cpu));}
static void htab_dtor_ctx_free(void *ctx){ struct htab_btf_record *hrec = ctx;
btf_record_free(hrec->record); kfree(ctx);}
static int bpf_ma_set_dtor(struct bpf_map *map, struct bpf_mem_alloc *ma, void (*dtor)(void *, void *)){ struct htab_btf_record *hrec; int err;
/* No need for dtors. */ if (IS_ERR_OR_NULL(map->record)) return 0;
hrec = kzalloc(sizeof(*hrec), GFP_KERNEL); if (!hrec) return -ENOMEM; hrec->key_size = map->key_size; hrec->record = btf_record_dup(map->record); if (IS_ERR(hrec->record)) { err = PTR_ERR(hrec->record); kfree(hrec); return err; } bpf_mem_alloc_set_dtor(ma, dtor, htab_dtor_ctx_free, hrec); return 0;}
static int htab_map_check_btf(struct bpf_map *map, const struct btf *btf, const struct btf_type *key_type, const struct btf_type *value_type){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
if (htab_is_prealloc(htab)) return 0; /* * We must set the dtor using this callback, as map's BTF record is not * populated in htab_map_alloc(), so it will always appear as NULL. */ if (htab_is_percpu(htab)) return bpf_ma_set_dtor(map, &htab->pcpu_ma, htab_pcpu_mem_dtor); else return bpf_ma_set_dtor(map, &htab->ma, htab_mem_dtor);}
static struct bpf_map *htab_map_alloc(union bpf_attr *attr){ bool percpu = (attr->map_type == BPF_MAP_TYPE_PERCPU_HASH || attr->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH); /* percpu_lru means each cpu has its own LRU list. * it is different from BPF_MAP_TYPE_PERCPU_HASH where * the map's value itself is percpu. percpu_lru has * nothing to do with the map's value. */ bool percpu_lru = (attr->map_flags & BPF_F_NO_COMMON_LRU); bool prealloc = !(attr->map_flags & BPF_F_NO_PREALLOC); struct bpf_htab *htab; int err;
htab = bpf_map_area_alloc(sizeof(*htab), NUMA_NO_NODE); if (!htab) return ERR_PTR(-ENOMEM);
bpf_map_init_from_attr(&htab->map, attr);
if (percpu_lru) { /* ensure each CPU's lru list has >=1 elements. * since we are at it, make each lru list has the same * number of elements. */ htab->map.max_entries = roundup(attr->max_entries, num_possible_cpus()); if (htab->map.max_entries < attr->max_entries) htab->map.max_entries = rounddown(attr->max_entries, num_possible_cpus()); }
/* hash table size must be power of 2; roundup_pow_of_two() can overflow * into UB on 32-bit arches, so check that first */ err = -E2BIG; if (htab->map.max_entries > 1UL << 31) goto free_htab;
htab->n_buckets = roundup_pow_of_two(htab->map.max_entries);
htab->elem_size = sizeof(struct htab_elem) + round_up(htab->map.key_size, 8); if (percpu) htab->elem_size += sizeof(void *); else htab->elem_size += round_up(htab->map.value_size, 8);
/* check for u32 overflow */ if (htab->n_buckets > U32_MAX / sizeof(struct bucket)) goto free_htab;
err = bpf_map_init_elem_count(&htab->map); if (err) goto free_htab;
err = -ENOMEM; htab->buckets = bpf_map_area_alloc(htab->n_buckets * sizeof(struct bucket), htab->map.numa_node); if (!htab->buckets) goto free_elem_count;
if (htab->map.map_flags & BPF_F_ZERO_SEED) htab->hashrnd = 0; else htab->hashrnd = get_random_u32();
htab_init_buckets(htab);
/* compute_batch_value() computes batch value as num_online_cpus() * 2 * and __percpu_counter_compare() needs * htab->max_entries - cur_number_of_elems to be more than batch * num_online_cpus() * for percpu_counter to be faster than atomic_t. In practice the average bpf * hash map size is 10k, which means that a system with 64 cpus will fill * hashmap to 20% of 10k before percpu_counter becomes ineffective. Therefore * define our own batch count as 32 then 10k hash map can be filled up to 80%: * 10k - 8k > 32 _batch_ * 64 _cpus_ * and __percpu_counter_compare() will still be fast. At that point hash map * collisions will dominate its performance anyway. Assume that hash map filled * to 50+% isn't going to be O(1) and use the following formula to choose * between percpu_counter and atomic_t. */#define PERCPU_COUNTER_BATCH 32 if (attr->max_entries / 2 > num_online_cpus() * PERCPU_COUNTER_BATCH) htab->use_percpu_counter = true;
if (htab->use_percpu_counter) { err = percpu_counter_init(&htab->pcount, 0, GFP_KERNEL); if (err) goto free_map_locked; }
if (prealloc) { err = prealloc_init(htab); if (err) goto free_map_locked;
if (htab_has_extra_elems(htab)) { err = alloc_extra_elems(htab); if (err) goto free_prealloc; } } else { err = bpf_mem_alloc_init(&htab->ma, htab->elem_size, false); if (err) goto free_map_locked; if (percpu) { err = bpf_mem_alloc_init(&htab->pcpu_ma, round_up(htab->map.value_size, 8), true); if (err) goto free_map_locked; } }
return &htab->map;
free_prealloc: prealloc_destroy(htab);free_map_locked: if (htab->use_percpu_counter) percpu_counter_destroy(&htab->pcount); bpf_map_area_free(htab->buckets); bpf_mem_alloc_destroy(&htab->pcpu_ma); bpf_mem_alloc_destroy(&htab->ma);free_elem_count: bpf_map_free_elem_count(&htab->map);free_htab: bpf_map_area_free(htab); return ERR_PTR(err);}
static inline u32 htab_map_hash(const void *key, u32 key_len, u32 hashrnd){ if (likely(key_len % 4 == 0)) return jhash2(key, key_len / 4, hashrnd); return jhash(key, key_len, hashrnd);}
static inline struct bucket *__select_bucket(struct bpf_htab *htab, u32 hash){ return &htab->buckets[hash & (htab->n_buckets - 1)];}
static inline struct hlist_nulls_head *select_bucket(struct bpf_htab *htab, u32 hash){ return &__select_bucket(htab, hash)->head;}
/* this lookup function can only be called with bucket lock taken */static struct htab_elem *lookup_elem_raw(struct hlist_nulls_head *head, u32 hash, void *key, u32 key_size){ struct hlist_nulls_node *n; struct htab_elem *l;
hlist_nulls_for_each_entry_rcu(l, n, head, hash_node) if (l->hash == hash && !memcmp(&l->key, key, key_size)) return l;
return NULL;}
/* can be called without bucket lock. it will repeat the loop in * the unlikely event when elements moved from one bucket into another * while link list is being walked */static struct htab_elem *lookup_nulls_elem_raw(struct hlist_nulls_head *head, u32 hash, void *key, u32 key_size, u32 n_buckets){ struct hlist_nulls_node *n; struct htab_elem *l;
again: hlist_nulls_for_each_entry_rcu(l, n, head, hash_node) if (l->hash == hash && !memcmp(&l->key, key, key_size)) return l;
if (unlikely(get_nulls_value(n) != (hash & (n_buckets - 1)))) goto again;
return NULL;}
/* Called from syscall or from eBPF program directly, so * arguments have to match bpf_map_lookup_elem() exactly. * The return value is adjusted by BPF instructions * in htab_map_gen_lookup(). */static void *__htab_map_lookup_elem(struct bpf_map *map, void *key){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct hlist_nulls_head *head; struct htab_elem *l; u32 hash, key_size;
WARN_ON_ONCE(!bpf_rcu_lock_held());
key_size = map->key_size;
hash = htab_map_hash(key, key_size, htab->hashrnd);
head = select_bucket(htab, hash);
l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);
return l;}
static void *htab_map_lookup_elem(struct bpf_map *map, void *key){ struct htab_elem *l = __htab_map_lookup_elem(map, key);
if (l) return htab_elem_value(l, map->key_size);
return NULL;}
/* inline bpf_map_lookup_elem() call. * Instead of: * bpf_prog * bpf_map_lookup_elem * map->ops->map_lookup_elem * htab_map_lookup_elem * __htab_map_lookup_elem * do: * bpf_prog * __htab_map_lookup_elem */static int htab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf){ struct bpf_insn *insn = insn_buf; const int ret = BPF_REG_0;
BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem, (void *(*)(struct bpf_map *map, void *key))NULL)); *insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem); *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1); *insn++ = BPF_ALU64_IMM(BPF_ADD, ret, offsetof(struct htab_elem, key) + round_up(map->key_size, 8)); return insn - insn_buf;}
static __always_inline void *__htab_lru_map_lookup_elem(struct bpf_map *map, void *key, const bool mark){ struct htab_elem *l = __htab_map_lookup_elem(map, key);
if (l) { if (mark) bpf_lru_node_set_ref(&l->lru_node); return htab_elem_value(l, map->key_size); }
return NULL;}
static void *htab_lru_map_lookup_elem(struct bpf_map *map, void *key){ return __htab_lru_map_lookup_elem(map, key, true);}
static void *htab_lru_map_lookup_elem_sys(struct bpf_map *map, void *key){ return __htab_lru_map_lookup_elem(map, key, false);}
static int htab_lru_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf){ struct bpf_insn *insn = insn_buf; const int ret = BPF_REG_0; const int ref_reg = BPF_REG_1;
BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem, (void *(*)(struct bpf_map *map, void *key))NULL)); *insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem); *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 4); *insn++ = BPF_LDX_MEM(BPF_B, ref_reg, ret, offsetof(struct htab_elem, lru_node) + offsetof(struct bpf_lru_node, ref)); *insn++ = BPF_JMP_IMM(BPF_JNE, ref_reg, 0, 1); *insn++ = BPF_ST_MEM(BPF_B, ret, offsetof(struct htab_elem, lru_node) + offsetof(struct bpf_lru_node, ref), 1); *insn++ = BPF_ALU64_IMM(BPF_ADD, ret, offsetof(struct htab_elem, key) + round_up(map->key_size, 8)); return insn - insn_buf;}
static void check_and_cancel_fields(struct bpf_htab *htab, struct htab_elem *elem){ if (IS_ERR_OR_NULL(htab->map.record)) return;
if (htab_is_percpu(htab)) { void __percpu *pptr = htab_elem_get_ptr(elem, htab->map.key_size); int cpu;
for_each_possible_cpu(cpu) bpf_obj_cancel_fields(&htab->map, per_cpu_ptr(pptr, cpu)); } else { void *map_value = htab_elem_value(elem, htab->map.key_size);
bpf_obj_cancel_fields(&htab->map, map_value); }}
/* It is called from the bpf_lru_list when the LRU needs to delete * older elements from the htab. */static bool htab_lru_map_delete_node(void *arg, struct bpf_lru_node *node){ struct bpf_htab *htab = arg; struct htab_elem *l = NULL, *tgt_l; struct hlist_nulls_head *head; struct hlist_nulls_node *n; unsigned long flags; struct bucket *b; int ret;
tgt_l = container_of(node, struct htab_elem, lru_node); b = __select_bucket(htab, tgt_l->hash); head = &b->head;
ret = htab_lock_bucket(b, &flags); if (ret) return false;
hlist_nulls_for_each_entry_rcu(l, n, head, hash_node) if (l == tgt_l) { hlist_nulls_del_rcu(&l->hash_node); bpf_map_dec_elem_count(&htab->map); break; }
htab_unlock_bucket(b, flags);
if (l == tgt_l) check_and_cancel_fields(htab, l); return l == tgt_l;}
/* Called from syscall */static int htab_map_get_next_key(struct bpf_map *map, void *key, void *next_key){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct hlist_nulls_head *head; struct htab_elem *l, *next_l; u32 hash, key_size; int i = 0;
WARN_ON_ONCE(!rcu_read_lock_held());
key_size = map->key_size;
if (!key) goto find_first_elem;
hash = htab_map_hash(key, key_size, htab->hashrnd);
head = select_bucket(htab, hash);
/* lookup the key */ l = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets);
if (!l) goto find_first_elem;
/* key was found, get next key in the same bucket */ next_l = hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_next_rcu(&l->hash_node)), struct htab_elem, hash_node);
if (next_l) { /* if next elem in this hash list is non-zero, just return it */ memcpy(next_key, next_l->key, key_size); return 0; }
/* no more elements in this hash list, go to the next bucket */ i = hash & (htab->n_buckets - 1); i++;
find_first_elem: /* iterate over buckets */ for (; i < htab->n_buckets; i++) { head = select_bucket(htab, i);
/* pick first element in the bucket */ next_l = hlist_nulls_entry_safe(rcu_dereference_raw(hlist_nulls_first_rcu(head)), struct htab_elem, hash_node); if (next_l) { /* if it's not empty, just return it */ memcpy(next_key, next_l->key, key_size); return 0; } }
/* iterated over all buckets and all elements */ return -ENOENT;}
static void htab_elem_free(struct bpf_htab *htab, struct htab_elem *l){ check_and_cancel_fields(htab, l);
if (htab->map.map_type == BPF_MAP_TYPE_PERCPU_HASH) bpf_mem_cache_free(&htab->pcpu_ma, l->ptr_to_pptr); bpf_mem_cache_free(&htab->ma, l);}
static void htab_put_fd_value(struct bpf_htab *htab, struct htab_elem *l){ struct bpf_map *map = &htab->map; void *ptr;
if (map->ops->map_fd_put_ptr) { ptr = fd_htab_map_get_ptr(map, l); map->ops->map_fd_put_ptr(map, ptr, true); }}
static bool is_map_full(struct bpf_htab *htab){ if (htab->use_percpu_counter) return __percpu_counter_compare(&htab->pcount, htab->map.max_entries, PERCPU_COUNTER_BATCH) >= 0; return atomic_read(&htab->count) >= htab->map.max_entries;}
static void inc_elem_count(struct bpf_htab *htab){ bpf_map_inc_elem_count(&htab->map);
if (htab->use_percpu_counter) percpu_counter_add_batch(&htab->pcount, 1, PERCPU_COUNTER_BATCH); else atomic_inc(&htab->count);}
static void dec_elem_count(struct bpf_htab *htab){ bpf_map_dec_elem_count(&htab->map);
if (htab->use_percpu_counter) percpu_counter_add_batch(&htab->pcount, -1, PERCPU_COUNTER_BATCH); else atomic_dec(&htab->count);}
static void free_htab_elem(struct bpf_htab *htab, struct htab_elem *l){ htab_put_fd_value(htab, l);
if (htab_is_prealloc(htab)) { bpf_map_dec_elem_count(&htab->map); check_and_cancel_fields(htab, l); pcpu_freelist_push(&htab->freelist, &l->fnode); } else { dec_elem_count(htab); htab_elem_free(htab, l); }}
static void pcpu_copy_value(struct bpf_htab *htab, void __percpu *pptr, void *value, bool onallcpus, u64 map_flags){ void *ptr;
if (!onallcpus) { /* copy true value_size bytes */ ptr = this_cpu_ptr(pptr); copy_map_value(&htab->map, ptr, value); bpf_obj_cancel_fields(&htab->map, ptr); } else { u32 size = round_up(htab->map.value_size, 8); void *val; int cpu;
if (map_flags & BPF_F_CPU) { cpu = map_flags >> 32; ptr = per_cpu_ptr(pptr, cpu); copy_map_value(&htab->map, ptr, value); bpf_obj_cancel_fields(&htab->map, ptr); return; }
for_each_possible_cpu(cpu) { ptr = per_cpu_ptr(pptr, cpu); val = (map_flags & BPF_F_ALL_CPUS) ? value : value + size * cpu; copy_map_value(&htab->map, ptr, val); bpf_obj_cancel_fields(&htab->map, ptr); } }}
static void pcpu_init_value(struct bpf_htab *htab, void __percpu *pptr, void *value, bool onallcpus, u64 map_flags){ /* When not setting the initial value on all cpus, zero-fill element * values for other cpus. Otherwise, bpf program has no way to ensure * known initial values for cpus other than current one * (onallcpus=false always when coming from bpf prog). */ if (!onallcpus) { int current_cpu = raw_smp_processor_id(); int cpu;
for_each_possible_cpu(cpu) { if (cpu == current_cpu) copy_map_value(&htab->map, per_cpu_ptr(pptr, cpu), value); else /* Since elem is preallocated, we cannot touch special fields */ zero_map_value(&htab->map, per_cpu_ptr(pptr, cpu)); } } else { pcpu_copy_value(htab, pptr, value, onallcpus, map_flags); }}
static bool fd_htab_map_needs_adjust(const struct bpf_htab *htab){ return is_fd_htab(htab) && BITS_PER_LONG == 64;}
static struct htab_elem *alloc_htab_elem(struct bpf_htab *htab, void *key, void *value, u32 key_size, u32 hash, bool percpu, bool onallcpus, struct htab_elem *old_elem, u64 map_flags){ u32 size = htab->map.value_size; bool prealloc = htab_is_prealloc(htab); struct htab_elem *l_new, **pl_new; void __percpu *pptr;
if (prealloc) { if (old_elem) { /* if we're updating the existing element, * use per-cpu extra elems to avoid freelist_pop/push */ pl_new = this_cpu_ptr(htab->extra_elems); l_new = *pl_new; *pl_new = old_elem; } else { struct pcpu_freelist_node *l;
l = __pcpu_freelist_pop(&htab->freelist); if (!l) return ERR_PTR(-E2BIG); l_new = container_of(l, struct htab_elem, fnode); bpf_map_inc_elem_count(&htab->map); } } else { if (is_map_full(htab)) if (!old_elem) /* when map is full and update() is replacing * old element, it's ok to allocate, since * old element will be freed immediately. * Otherwise return an error */ return ERR_PTR(-E2BIG); inc_elem_count(htab); l_new = bpf_mem_cache_alloc(&htab->ma); if (!l_new) { l_new = ERR_PTR(-ENOMEM); goto dec_count; } }
memcpy(l_new->key, key, key_size); if (percpu) { if (prealloc) { pptr = htab_elem_get_ptr(l_new, key_size); } else { /* alloc_percpu zero-fills */ void *ptr = bpf_mem_cache_alloc(&htab->pcpu_ma);
if (!ptr) { bpf_mem_cache_free(&htab->ma, l_new); l_new = ERR_PTR(-ENOMEM); goto dec_count; } l_new->ptr_to_pptr = ptr; pptr = *(void __percpu **)ptr; }
pcpu_init_value(htab, pptr, value, onallcpus, map_flags);
if (!prealloc) htab_elem_set_ptr(l_new, key_size, pptr); } else if (fd_htab_map_needs_adjust(htab)) { size = round_up(size, 8); memcpy(htab_elem_value(l_new, key_size), value, size); } else if (map_flags & BPF_F_LOCK) { copy_map_value_locked(&htab->map, htab_elem_value(l_new, key_size), value, false); } else { copy_map_value(&htab->map, htab_elem_value(l_new, key_size), value); }
l_new->hash = hash; return l_new;dec_count: dec_elem_count(htab); return l_new;}
static int check_flags(struct bpf_htab *htab, struct htab_elem *l_old, u64 map_flags){ if (l_old && (map_flags & ~BPF_F_LOCK) == BPF_NOEXIST) /* elem already exists */ return -EEXIST;
if (!l_old && (map_flags & ~BPF_F_LOCK) == BPF_EXIST) /* elem doesn't exist, cannot update it */ return -ENOENT;
return 0;}
/* Called from syscall or from eBPF program */static long htab_map_update_elem(struct bpf_map *map, void *key, void *value, u64 map_flags){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct htab_elem *l_new, *l_old; struct hlist_nulls_head *head; unsigned long flags; struct bucket *b; u32 key_size, hash; int ret;
if (unlikely((map_flags & ~BPF_F_LOCK) > BPF_EXIST)) /* unknown flags */ return -EINVAL;
WARN_ON_ONCE(!bpf_rcu_lock_held());
key_size = map->key_size;
hash = htab_map_hash(key, key_size, htab->hashrnd);
b = __select_bucket(htab, hash); head = &b->head;
if (unlikely(map_flags & BPF_F_LOCK)) { if (unlikely(!btf_record_has_field(map->record, BPF_SPIN_LOCK))) return -EINVAL; /* find an element without taking the bucket lock */ l_old = lookup_nulls_elem_raw(head, hash, key, key_size, htab->n_buckets); ret = check_flags(htab, l_old, map_flags); if (ret) return ret; if (l_old) { /* grab the element lock and update value in place */ copy_map_value_locked(map, htab_elem_value(l_old, key_size), value, false); return 0; } /* fall through, grab the bucket lock and lookup again. * 99.9% chance that the element won't be found, * but second lookup under lock has to be done. */ }
ret = htab_lock_bucket(b, &flags); if (ret) return ret;
l_old = lookup_elem_raw(head, hash, key, key_size);
ret = check_flags(htab, l_old, map_flags); if (ret) goto err;
if (unlikely(l_old && (map_flags & BPF_F_LOCK))) { /* first lookup without the bucket lock didn't find the element, * but second lookup with the bucket lock found it. * This case is highly unlikely, but has to be dealt with: * grab the element lock in addition to the bucket lock * and update element in place */ copy_map_value_locked(map, htab_elem_value(l_old, key_size), value, false); ret = 0; goto err; }
l_new = alloc_htab_elem(htab, key, value, key_size, hash, false, false, l_old, map_flags); if (IS_ERR(l_new)) { /* all pre-allocated elements are in use or memory exhausted */ ret = PTR_ERR(l_new); goto err; }
/* add new element to the head of the list, so that * concurrent search will find it before old elem */ hlist_nulls_add_head_rcu(&l_new->hash_node, head); if (l_old) { hlist_nulls_del_rcu(&l_old->hash_node);
/* l_old has already been stashed in htab->extra_elems, cancel * its reusable special fields before it is available for reuse. */ if (htab_is_prealloc(htab)) check_and_cancel_fields(htab, l_old); } htab_unlock_bucket(b, flags); if (l_old && !htab_is_prealloc(htab)) free_htab_elem(htab, l_old); return 0;err: htab_unlock_bucket(b, flags); return ret;}
static void htab_lru_push_free(struct bpf_htab *htab, struct htab_elem *elem){ check_and_cancel_fields(htab, elem); bpf_map_dec_elem_count(&htab->map); bpf_lru_push_free(&htab->lru, &elem->lru_node);}
static long htab_lru_map_update_elem(struct bpf_map *map, void *key, void *value, u64 map_flags){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct htab_elem *l_new, *l_old = NULL; struct hlist_nulls_head *head; unsigned long flags; struct bucket *b; u32 key_size, hash; int ret;
if (unlikely(map_flags > BPF_EXIST)) /* unknown flags */ return -EINVAL;
WARN_ON_ONCE(!bpf_rcu_lock_held());
key_size = map->key_size;
hash = htab_map_hash(key, key_size, htab->hashrnd);
b = __select_bucket(htab, hash); head = &b->head;
/* For LRU, we need to alloc before taking bucket's * spinlock because getting free nodes from LRU may need * to remove older elements from htab and this removal * operation will need a bucket lock. */ l_new = prealloc_lru_pop(htab, key, hash); if (!l_new) return -ENOMEM; copy_map_value(&htab->map, htab_elem_value(l_new, map->key_size), value);
ret = htab_lock_bucket(b, &flags); if (ret) goto err_lock_bucket;
l_old = lookup_elem_raw(head, hash, key, key_size);
ret = check_flags(htab, l_old, map_flags); if (ret) goto err;
/* add new element to the head of the list, so that * concurrent search will find it before old elem */ hlist_nulls_add_head_rcu(&l_new->hash_node, head); if (l_old) { bpf_lru_node_set_ref(&l_new->lru_node); hlist_nulls_del_rcu(&l_old->hash_node); } ret = 0;
err: htab_unlock_bucket(b, flags);
err_lock_bucket: if (ret) htab_lru_push_free(htab, l_new); else if (l_old) htab_lru_push_free(htab, l_old);
return ret;}
static int htab_map_check_update_flags(bool onallcpus, u64 map_flags){ if (unlikely(!onallcpus && map_flags > BPF_EXIST)) return -EINVAL; if (unlikely(onallcpus && ((map_flags & BPF_F_LOCK) || (u32)map_flags > BPF_F_ALL_CPUS))) return -EINVAL; return 0;}
static long htab_map_update_elem_in_place(struct bpf_map *map, void *key, void *value, u64 map_flags, bool percpu, bool onallcpus){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct htab_elem *l_new, *l_old; struct hlist_nulls_head *head; void *old_map_ptr = NULL; unsigned long flags; struct bucket *b; u32 key_size, hash; int ret;
ret = htab_map_check_update_flags(onallcpus, map_flags); if (unlikely(ret)) return ret;
WARN_ON_ONCE(!bpf_rcu_lock_held());
key_size = map->key_size;
hash = htab_map_hash(key, key_size, htab->hashrnd);
b = __select_bucket(htab, hash); head = &b->head;
ret = htab_lock_bucket(b, &flags); if (ret) return ret;
l_old = lookup_elem_raw(head, hash, key, key_size);
ret = check_flags(htab, l_old, map_flags); if (ret) goto err;
if (l_old) { /* Update value in-place */ if (percpu) { pcpu_copy_value(htab, htab_elem_get_ptr(l_old, key_size), value, onallcpus, map_flags); } else { void **inner_map_pptr = htab_elem_value(l_old, key_size);
old_map_ptr = *inner_map_pptr; WRITE_ONCE(*inner_map_pptr, *(void **)value); } } else { l_new = alloc_htab_elem(htab, key, value, key_size, hash, percpu, onallcpus, NULL, map_flags); if (IS_ERR(l_new)) { ret = PTR_ERR(l_new); goto err; } hlist_nulls_add_head_rcu(&l_new->hash_node, head); }err: htab_unlock_bucket(b, flags); if (old_map_ptr) map->ops->map_fd_put_ptr(map, old_map_ptr, true); return ret;}
static long __htab_lru_percpu_map_update_elem(struct bpf_map *map, void *key, void *value, u64 map_flags, bool onallcpus){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct htab_elem *l_new = NULL, *l_old; struct hlist_nulls_head *head; unsigned long flags; struct bucket *b; u32 key_size, hash; int ret;
ret = htab_map_check_update_flags(onallcpus, map_flags); if (unlikely(ret)) return ret;
WARN_ON_ONCE(!bpf_rcu_lock_held());
key_size = map->key_size;
hash = htab_map_hash(key, key_size, htab->hashrnd);
b = __select_bucket(htab, hash); head = &b->head;
/* For LRU, we need to alloc before taking bucket's * spinlock because LRU's elem alloc may need * to remove older elem from htab and this removal * operation will need a bucket lock. */ if (map_flags != BPF_EXIST) { l_new = prealloc_lru_pop(htab, key, hash); if (!l_new) return -ENOMEM; }
ret = htab_lock_bucket(b, &flags); if (ret) goto err_lock_bucket;
l_old = lookup_elem_raw(head, hash, key, key_size);
ret = check_flags(htab, l_old, map_flags); if (ret) goto err;
if (l_old) { bpf_lru_node_set_ref(&l_old->lru_node);
/* per-cpu hash map can update value in-place */ pcpu_copy_value(htab, htab_elem_get_ptr(l_old, key_size), value, onallcpus, map_flags); } else { pcpu_init_value(htab, htab_elem_get_ptr(l_new, key_size), value, onallcpus, map_flags); hlist_nulls_add_head_rcu(&l_new->hash_node, head); l_new = NULL; } ret = 0;err: htab_unlock_bucket(b, flags);err_lock_bucket: if (l_new) { bpf_map_dec_elem_count(&htab->map); bpf_lru_push_free(&htab->lru, &l_new->lru_node); } return ret;}
static long htab_percpu_map_update_elem(struct bpf_map *map, void *key, void *value, u64 map_flags){ return htab_map_update_elem_in_place(map, key, value, map_flags, true, false);}
static long htab_lru_percpu_map_update_elem(struct bpf_map *map, void *key, void *value, u64 map_flags){ return __htab_lru_percpu_map_update_elem(map, key, value, map_flags, false);}
/* Called from syscall or from eBPF program */static long htab_map_delete_elem(struct bpf_map *map, void *key){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct hlist_nulls_head *head; struct bucket *b; struct htab_elem *l; unsigned long flags; u32 hash, key_size; int ret;
WARN_ON_ONCE(!bpf_rcu_lock_held());
key_size = map->key_size;
hash = htab_map_hash(key, key_size, htab->hashrnd); b = __select_bucket(htab, hash); head = &b->head;
ret = htab_lock_bucket(b, &flags); if (ret) return ret;
l = lookup_elem_raw(head, hash, key, key_size); if (l) hlist_nulls_del_rcu(&l->hash_node); else ret = -ENOENT;
htab_unlock_bucket(b, flags);
if (l) free_htab_elem(htab, l); return ret;}
static long htab_lru_map_delete_elem(struct bpf_map *map, void *key){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct hlist_nulls_head *head; struct bucket *b; struct htab_elem *l; unsigned long flags; u32 hash, key_size; int ret;
WARN_ON_ONCE(!bpf_rcu_lock_held());
key_size = map->key_size;
hash = htab_map_hash(key, key_size, htab->hashrnd); b = __select_bucket(htab, hash); head = &b->head;
ret = htab_lock_bucket(b, &flags); if (ret) return ret;
l = lookup_elem_raw(head, hash, key, key_size);
if (l) hlist_nulls_del_rcu(&l->hash_node); else ret = -ENOENT;
htab_unlock_bucket(b, flags); if (l) htab_lru_push_free(htab, l); return ret;}
static void delete_all_elements(struct bpf_htab *htab){ int i;
/* It's called from a worker thread and migration has been disabled, * therefore, it is OK to invoke bpf_mem_cache_free() directly. */ for (i = 0; i < htab->n_buckets; i++) { struct hlist_nulls_head *head = select_bucket(htab, i); struct hlist_nulls_node *n; struct htab_elem *l;
hlist_nulls_for_each_entry_safe(l, n, head, hash_node) { hlist_nulls_del_rcu(&l->hash_node); htab_elem_free(htab, l); } cond_resched(); }}
static void htab_free_malloced_internal_structs(struct bpf_htab *htab){ int i;
rcu_read_lock(); for (i = 0; i < htab->n_buckets; i++) { struct hlist_nulls_head *head = select_bucket(htab, i); struct hlist_nulls_node *n; struct htab_elem *l;
hlist_nulls_for_each_entry(l, n, head, hash_node) { /* We only free internal structs on uref dropping to zero */ bpf_map_free_internal_structs(&htab->map, htab_elem_value(l, htab->map.key_size)); } cond_resched_rcu(); } rcu_read_unlock();}
static void htab_map_free_internal_structs(struct bpf_map *map){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
/* We only free internal structs on uref dropping to zero */ if (!bpf_map_has_internal_structs(map)) return;
if (htab_is_prealloc(htab)) htab_free_prealloced_internal_structs(htab); else htab_free_malloced_internal_structs(htab);}
/* Called when map->refcnt goes to zero, either from workqueue or from syscall */static void htab_map_free(struct bpf_map *map){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map);
/* bpf_free_used_maps() or close(map_fd) will trigger this map_free callback. * bpf_free_used_maps() is called after bpf prog is no longer executing. * There is no need to synchronize_rcu() here to protect map elements. */
/* htab no longer uses call_rcu() directly. bpf_mem_alloc does it * underneath and is responsible for waiting for callbacks to finish * during bpf_mem_alloc_destroy(). */ if (!htab_is_prealloc(htab)) { delete_all_elements(htab); } else { htab_free_prealloced_fields(htab); prealloc_destroy(htab); }
bpf_map_free_elem_count(map); free_percpu(htab->extra_elems); bpf_map_area_free(htab->buckets); bpf_mem_alloc_destroy(&htab->pcpu_ma); bpf_mem_alloc_destroy(&htab->ma); if (htab->use_percpu_counter) percpu_counter_destroy(&htab->pcount); bpf_map_area_free(htab);}
static void htab_map_seq_show_elem(struct bpf_map *map, void *key, struct seq_file *m){ void *value;
rcu_read_lock();
value = htab_map_lookup_elem(map, key); if (!value) { rcu_read_unlock(); return; }
btf_type_seq_show(map->btf, map->btf_key_type_id, key, m); seq_puts(m, ": "); btf_type_seq_show(map->btf, map->btf_value_type_id, value, m); seq_putc(m, '\n');
rcu_read_unlock();}
static int __htab_map_lookup_and_delete_elem(struct bpf_map *map, void *key, void *value, bool is_lru_map, bool is_percpu, u64 flags){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct hlist_nulls_head *head; unsigned long bflags; struct htab_elem *l; u32 hash, key_size; struct bucket *b; int ret;
key_size = map->key_size;
hash = htab_map_hash(key, key_size, htab->hashrnd); b = __select_bucket(htab, hash); head = &b->head;
ret = htab_lock_bucket(b, &bflags); if (ret) return ret;
l = lookup_elem_raw(head, hash, key, key_size); if (!l) { ret = -ENOENT; goto out_unlock; }
if (is_percpu) { u32 roundup_value_size = round_up(map->value_size, 8); void __percpu *pptr; int off = 0, cpu;
pptr = htab_elem_get_ptr(l, key_size); for_each_possible_cpu(cpu) { copy_map_value_long(&htab->map, value + off, per_cpu_ptr(pptr, cpu)); check_and_init_map_value(&htab->map, value + off); off += roundup_value_size; } } else { void *src = htab_elem_value(l, map->key_size);
if (flags & BPF_F_LOCK) copy_map_value_locked(map, value, src, true); else copy_map_value(map, value, src); /* Zeroing special fields in the temp buffer */ check_and_init_map_value(map, value); } hlist_nulls_del_rcu(&l->hash_node);
out_unlock: htab_unlock_bucket(b, bflags);
if (l) { if (is_lru_map) htab_lru_push_free(htab, l); else free_htab_elem(htab, l); }
return ret;}
static int htab_map_lookup_and_delete_elem(struct bpf_map *map, void *key, void *value, u64 flags){ return __htab_map_lookup_and_delete_elem(map, key, value, false, false, flags);}
static int htab_percpu_map_lookup_and_delete_elem(struct bpf_map *map, void *key, void *value, u64 flags){ return __htab_map_lookup_and_delete_elem(map, key, value, false, true, flags);}
static int htab_lru_map_lookup_and_delete_elem(struct bpf_map *map, void *key, void *value, u64 flags){ return __htab_map_lookup_and_delete_elem(map, key, value, true, false, flags);}
static int htab_lru_percpu_map_lookup_and_delete_elem(struct bpf_map *map, void *key, void *value, u64 flags){ return __htab_map_lookup_and_delete_elem(map, key, value, true, true, flags);}
static int__htab_map_lookup_and_delete_batch(struct bpf_map *map, const union bpf_attr *attr, union bpf_attr __user *uattr, bool do_delete, bool is_lru_map, bool is_percpu){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); void *keys = NULL, *values = NULL, *value, *dst_key, *dst_val; void __user *uvalues = u64_to_user_ptr(attr->batch.values); void __user *ukeys = u64_to_user_ptr(attr->batch.keys); void __user *ubatch = u64_to_user_ptr(attr->batch.in_batch); u32 batch, max_count, size, bucket_size, map_id; u64 elem_map_flags, map_flags, allowed_flags; u32 bucket_cnt, total, key_size, value_size; struct htab_elem *node_to_free = NULL; struct hlist_nulls_head *head; struct hlist_nulls_node *n; unsigned long flags = 0; bool locked = false; struct htab_elem *l; struct bucket *b; int ret = 0;
elem_map_flags = attr->batch.elem_flags; allowed_flags = BPF_F_LOCK; if (!do_delete && is_percpu) allowed_flags |= BPF_F_CPU; ret = bpf_map_check_op_flags(map, elem_map_flags, allowed_flags); if (ret) return ret;
map_flags = attr->batch.flags; if (map_flags) return -EINVAL;
max_count = attr->batch.count; if (!max_count) return 0;
if (put_user(0, &uattr->batch.count)) return -EFAULT;
batch = 0; if (ubatch && copy_from_user(&batch, ubatch, sizeof(batch))) return -EFAULT;
if (batch >= htab->n_buckets) return -ENOENT;
key_size = htab->map.key_size; value_size = htab->map.value_size; size = round_up(value_size, 8); if (is_percpu && !(elem_map_flags & BPF_F_CPU)) value_size = size * num_possible_cpus(); total = 0; /* while experimenting with hash tables with sizes ranging from 10 to * 1000, it was observed that a bucket can have up to 5 entries. */ bucket_size = 5;
alloc: /* We cannot do copy_from_user or copy_to_user inside * the rcu_read_lock. Allocate enough space here. */ keys = kvmalloc_array(key_size, bucket_size, GFP_USER | __GFP_NOWARN); values = kvmalloc_array(value_size, bucket_size, GFP_USER | __GFP_NOWARN); if (!keys || !values) { ret = -ENOMEM; goto after_loop; }
again: bpf_disable_instrumentation(); rcu_read_lock();again_nocopy: dst_key = keys; dst_val = values; b = &htab->buckets[batch]; head = &b->head; /* do not grab the lock unless need it (bucket_cnt > 0). */ if (locked) { ret = htab_lock_bucket(b, &flags); if (ret) { rcu_read_unlock(); bpf_enable_instrumentation(); goto after_loop; } }
bucket_cnt = 0; hlist_nulls_for_each_entry_rcu(l, n, head, hash_node) bucket_cnt++;
if (bucket_cnt && !locked) { locked = true; goto again_nocopy; }
if (bucket_cnt > (max_count - total)) { if (total == 0) ret = -ENOSPC; /* Note that since bucket_cnt > 0 here, it is implicit * that the locked was grabbed, so release it. */ htab_unlock_bucket(b, flags); rcu_read_unlock(); bpf_enable_instrumentation(); goto after_loop; }
if (bucket_cnt > bucket_size) { bucket_size = bucket_cnt; /* Note that since bucket_cnt > 0 here, it is implicit * that the locked was grabbed, so release it. */ htab_unlock_bucket(b, flags); rcu_read_unlock(); bpf_enable_instrumentation(); kvfree(keys); kvfree(values); goto alloc; }
/* Next block is only safe to run if you have grabbed the lock */ if (!locked) goto next_batch;
hlist_nulls_for_each_entry_safe(l, n, head, hash_node) { memcpy(dst_key, l->key, key_size);
if (is_percpu) { int off = 0, cpu; void __percpu *pptr;
pptr = htab_elem_get_ptr(l, map->key_size); if (elem_map_flags & BPF_F_CPU) { cpu = elem_map_flags >> 32; copy_map_value(&htab->map, dst_val, per_cpu_ptr(pptr, cpu)); check_and_init_map_value(&htab->map, dst_val); } else { for_each_possible_cpu(cpu) { copy_map_value_long(&htab->map, dst_val + off, per_cpu_ptr(pptr, cpu)); check_and_init_map_value(&htab->map, dst_val + off); off += size; } } } else { value = htab_elem_value(l, key_size); if (is_fd_htab(htab)) { struct bpf_map **inner_map = value;
/* Actual value is the id of the inner map */ map_id = map->ops->map_fd_sys_lookup_elem(*inner_map); value = &map_id; }
if (elem_map_flags & BPF_F_LOCK) copy_map_value_locked(map, dst_val, value, true); else copy_map_value(map, dst_val, value); /* Zeroing special fields in the temp buffer */ check_and_init_map_value(map, dst_val); } if (do_delete) { hlist_nulls_del_rcu(&l->hash_node);
/* bpf_lru_push_free() will acquire lru_lock, which * may cause deadlock. See comments in function * prealloc_lru_pop(). Let us do bpf_lru_push_free() * after releasing the bucket lock. * * For htab of maps, htab_put_fd_value() in * free_htab_elem() may acquire a spinlock with bucket * lock being held and it violates the lock rule, so * invoke free_htab_elem() after unlock as well. */ l->batch_flink = node_to_free; node_to_free = l; } dst_key += key_size; dst_val += value_size; }
htab_unlock_bucket(b, flags); locked = false;
while (node_to_free) { l = node_to_free; node_to_free = node_to_free->batch_flink; if (is_lru_map) htab_lru_push_free(htab, l); else free_htab_elem(htab, l); }
next_batch: /* If we are not copying data, we can go to next bucket and avoid * unlocking the rcu. */ if (!bucket_cnt && (batch + 1 < htab->n_buckets)) { batch++; goto again_nocopy; }
rcu_read_unlock(); bpf_enable_instrumentation(); if (bucket_cnt && (copy_to_user(ukeys + total * key_size, keys, key_size * bucket_cnt) || copy_to_user(uvalues + total * value_size, values, value_size * bucket_cnt))) { ret = -EFAULT; goto after_loop; }
total += bucket_cnt; batch++; if (batch >= htab->n_buckets) { ret = -ENOENT; goto after_loop; } goto again;
after_loop: if (ret == -EFAULT) goto out;
/* copy # of entries and next batch */ ubatch = u64_to_user_ptr(attr->batch.out_batch); if (copy_to_user(ubatch, &batch, sizeof(batch)) || put_user(total, &uattr->batch.count)) ret = -EFAULT;
out: kvfree(keys); kvfree(values); return ret;}
static inthtab_percpu_map_lookup_batch(struct bpf_map *map, const union bpf_attr *attr, union bpf_attr __user *uattr){ return __htab_map_lookup_and_delete_batch(map, attr, uattr, false, false, true);}
static inthtab_percpu_map_lookup_and_delete_batch(struct bpf_map *map, const union bpf_attr *attr, union bpf_attr __user *uattr){ return __htab_map_lookup_and_delete_batch(map, attr, uattr, true, false, true);}
static inthtab_map_lookup_batch(struct bpf_map *map, const union bpf_attr *attr, union bpf_attr __user *uattr){ return __htab_map_lookup_and_delete_batch(map, attr, uattr, false, false, false);}
static inthtab_map_lookup_and_delete_batch(struct bpf_map *map, const union bpf_attr *attr, union bpf_attr __user *uattr){ return __htab_map_lookup_and_delete_batch(map, attr, uattr, true, false, false);}
static inthtab_lru_percpu_map_lookup_batch(struct bpf_map *map, const union bpf_attr *attr, union bpf_attr __user *uattr){ return __htab_map_lookup_and_delete_batch(map, attr, uattr, false, true, true);}
static inthtab_lru_percpu_map_lookup_and_delete_batch(struct bpf_map *map, const union bpf_attr *attr, union bpf_attr __user *uattr){ return __htab_map_lookup_and_delete_batch(map, attr, uattr, true, true, true);}
static inthtab_lru_map_lookup_batch(struct bpf_map *map, const union bpf_attr *attr, union bpf_attr __user *uattr){ return __htab_map_lookup_and_delete_batch(map, attr, uattr, false, true, false);}
static inthtab_lru_map_lookup_and_delete_batch(struct bpf_map *map, const union bpf_attr *attr, union bpf_attr __user *uattr){ return __htab_map_lookup_and_delete_batch(map, attr, uattr, true, true, false);}
struct bpf_iter_seq_hash_map_info { struct bpf_map *map; struct bpf_htab *htab; void *percpu_value_buf; // non-zero means percpu hash u32 bucket_id; u32 skip_elems;};
static struct htab_elem *bpf_hash_map_seq_find_next(struct bpf_iter_seq_hash_map_info *info, struct htab_elem *prev_elem){ const struct bpf_htab *htab = info->htab; u32 skip_elems = info->skip_elems; u32 bucket_id = info->bucket_id; struct hlist_nulls_head *head; struct hlist_nulls_node *n; struct htab_elem *elem; struct bucket *b; u32 i, count;
if (bucket_id >= htab->n_buckets) return NULL;
/* try to find next elem in the same bucket */ if (prev_elem) { /* no update/deletion on this bucket, prev_elem should be still valid * and we won't skip elements. */ n = rcu_dereference_raw(hlist_nulls_next_rcu(&prev_elem->hash_node)); elem = hlist_nulls_entry_safe(n, struct htab_elem, hash_node); if (elem) return elem;
/* not found, unlock and go to the next bucket */ b = &htab->buckets[bucket_id++]; rcu_read_unlock(); skip_elems = 0; }
for (i = bucket_id; i < htab->n_buckets; i++) { b = &htab->buckets[i]; rcu_read_lock();
count = 0; head = &b->head; hlist_nulls_for_each_entry_rcu(elem, n, head, hash_node) { if (count >= skip_elems) { info->bucket_id = i; info->skip_elems = count; return elem; } count++; }
rcu_read_unlock(); skip_elems = 0; }
info->bucket_id = i; info->skip_elems = 0; return NULL;}
static void *bpf_hash_map_seq_start(struct seq_file *seq, loff_t *pos){ struct bpf_iter_seq_hash_map_info *info = seq->private; struct htab_elem *elem;
elem = bpf_hash_map_seq_find_next(info, NULL); if (!elem) return NULL;
if (*pos == 0) ++*pos; return elem;}
static void *bpf_hash_map_seq_next(struct seq_file *seq, void *v, loff_t *pos){ struct bpf_iter_seq_hash_map_info *info = seq->private;
++*pos; ++info->skip_elems; return bpf_hash_map_seq_find_next(info, v);}
static int __bpf_hash_map_seq_show(struct seq_file *seq, struct htab_elem *elem){ struct bpf_iter_seq_hash_map_info *info = seq->private; struct bpf_iter__bpf_map_elem ctx = {}; struct bpf_map *map = info->map; struct bpf_iter_meta meta; int ret = 0, off = 0, cpu; u32 roundup_value_size; struct bpf_prog *prog; void __percpu *pptr;
meta.seq = seq; prog = bpf_iter_get_info(&meta, elem == NULL); if (prog) { ctx.meta = &meta; ctx.map = info->map; if (elem) { ctx.key = elem->key; if (!info->percpu_value_buf) { ctx.value = htab_elem_value(elem, map->key_size); } else { roundup_value_size = round_up(map->value_size, 8); pptr = htab_elem_get_ptr(elem, map->key_size); for_each_possible_cpu(cpu) { copy_map_value_long(map, info->percpu_value_buf + off, per_cpu_ptr(pptr, cpu)); check_and_init_map_value(map, info->percpu_value_buf + off); off += roundup_value_size; } ctx.value = info->percpu_value_buf; } } ret = bpf_iter_run_prog(prog, &ctx); }
return ret;}
static int bpf_hash_map_seq_show(struct seq_file *seq, void *v){ return __bpf_hash_map_seq_show(seq, v);}
static void bpf_hash_map_seq_stop(struct seq_file *seq, void *v){ if (!v) (void)__bpf_hash_map_seq_show(seq, NULL); else rcu_read_unlock();}
static int bpf_iter_init_hash_map(void *priv_data, struct bpf_iter_aux_info *aux){ struct bpf_iter_seq_hash_map_info *seq_info = priv_data; struct bpf_map *map = aux->map; void *value_buf; u32 buf_size;
if (map->map_type == BPF_MAP_TYPE_PERCPU_HASH || map->map_type == BPF_MAP_TYPE_LRU_PERCPU_HASH) { buf_size = round_up(map->value_size, 8) * num_possible_cpus(); value_buf = kmalloc(buf_size, GFP_USER | __GFP_NOWARN); if (!value_buf) return -ENOMEM;
seq_info->percpu_value_buf = value_buf; }
bpf_map_inc_with_uref(map); seq_info->map = map; seq_info->htab = container_of(map, struct bpf_htab, map); return 0;}
static void bpf_iter_fini_hash_map(void *priv_data){ struct bpf_iter_seq_hash_map_info *seq_info = priv_data;
bpf_map_put_with_uref(seq_info->map); kfree(seq_info->percpu_value_buf);}
static const struct seq_operations bpf_hash_map_seq_ops = { .start = bpf_hash_map_seq_start, .next = bpf_hash_map_seq_next, .stop = bpf_hash_map_seq_stop, .show = bpf_hash_map_seq_show,};
static const struct bpf_iter_seq_info iter_seq_info = { .seq_ops = &bpf_hash_map_seq_ops, .init_seq_private = bpf_iter_init_hash_map, .fini_seq_private = bpf_iter_fini_hash_map, .seq_priv_size = sizeof(struct bpf_iter_seq_hash_map_info),};
static long bpf_for_each_hash_elem(struct bpf_map *map, bpf_callback_t callback_fn, void *callback_ctx, u64 flags){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct hlist_nulls_head *head; struct hlist_nulls_node *n; struct htab_elem *elem; int i, num_elems = 0; void __percpu *pptr; struct bucket *b; void *key, *val; bool is_percpu; u64 ret = 0;
cant_migrate();
if (flags != 0) return -EINVAL;
is_percpu = htab_is_percpu(htab);
/* migration has been disabled, so percpu value prepared here will be * the same as the one seen by the bpf program with * bpf_map_lookup_elem(). */ for (i = 0; i < htab->n_buckets; i++) { b = &htab->buckets[i]; rcu_read_lock(); head = &b->head; hlist_nulls_for_each_entry_safe(elem, n, head, hash_node) { key = elem->key; if (is_percpu) { /* current cpu value for percpu map */ pptr = htab_elem_get_ptr(elem, map->key_size); val = this_cpu_ptr(pptr); } else { val = htab_elem_value(elem, map->key_size); } num_elems++; ret = callback_fn((u64)(long)map, (u64)(long)key, (u64)(long)val, (u64)(long)callback_ctx, 0); /* return value: 0 - continue, 1 - stop and return */ if (ret) { rcu_read_unlock(); goto out; } } rcu_read_unlock(); }out: return num_elems;}
static u64 htab_map_mem_usage(const struct bpf_map *map){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); u32 value_size = round_up(htab->map.value_size, 8); bool prealloc = htab_is_prealloc(htab); bool percpu = htab_is_percpu(htab); bool lru = htab_is_lru(htab); u64 num_entries, usage;
usage = sizeof(struct bpf_htab) + sizeof(struct bucket) * htab->n_buckets;
if (prealloc) { num_entries = map->max_entries; if (htab_has_extra_elems(htab)) num_entries += num_possible_cpus();
usage += htab->elem_size * num_entries;
if (percpu) usage += value_size * num_possible_cpus() * num_entries; else if (!lru) usage += sizeof(struct htab_elem *) * num_possible_cpus(); } else {#define LLIST_NODE_SZ sizeof(struct llist_node)
num_entries = htab->use_percpu_counter ? percpu_counter_sum(&htab->pcount) : atomic_read(&htab->count); usage += (htab->elem_size + LLIST_NODE_SZ) * num_entries; if (percpu) { usage += (LLIST_NODE_SZ + sizeof(void *)) * num_entries; usage += value_size * num_possible_cpus() * num_entries; } } return usage;}
BTF_ID_LIST_SINGLE(htab_map_btf_ids, struct, bpf_htab)const struct bpf_map_ops htab_map_ops = { .map_meta_equal = bpf_map_meta_equal, .map_alloc_check = htab_map_alloc_check, .map_alloc = htab_map_alloc, .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_release_uref = htab_map_free_internal_structs, .map_lookup_elem = htab_map_lookup_elem, .map_lookup_and_delete_elem = htab_map_lookup_and_delete_elem, .map_update_elem = htab_map_update_elem, .map_delete_elem = htab_map_delete_elem, .map_gen_lookup = htab_map_gen_lookup, .map_seq_show_elem = htab_map_seq_show_elem, .map_set_for_each_callback_args = map_set_for_each_callback_args, .map_for_each_callback = bpf_for_each_hash_elem, .map_check_btf = htab_map_check_btf, .map_mem_usage = htab_map_mem_usage, BATCH_OPS(htab), .map_btf_id = &htab_map_btf_ids[0], .iter_seq_info = &iter_seq_info,};
const struct bpf_map_ops htab_lru_map_ops = { .map_meta_equal = bpf_map_meta_equal, .map_alloc_check = htab_map_alloc_check, .map_alloc = htab_map_alloc, .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_release_uref = htab_map_free_internal_structs, .map_lookup_elem = htab_lru_map_lookup_elem, .map_lookup_and_delete_elem = htab_lru_map_lookup_and_delete_elem, .map_lookup_elem_sys_only = htab_lru_map_lookup_elem_sys, .map_update_elem = htab_lru_map_update_elem, .map_delete_elem = htab_lru_map_delete_elem, .map_gen_lookup = htab_lru_map_gen_lookup, .map_seq_show_elem = htab_map_seq_show_elem, .map_set_for_each_callback_args = map_set_for_each_callback_args, .map_for_each_callback = bpf_for_each_hash_elem, .map_check_btf = htab_map_check_btf, .map_mem_usage = htab_map_mem_usage, BATCH_OPS(htab_lru), .map_btf_id = &htab_map_btf_ids[0], .iter_seq_info = &iter_seq_info,};
/* Called from eBPF program */static void *htab_percpu_map_lookup_elem(struct bpf_map *map, void *key){ struct htab_elem *l = __htab_map_lookup_elem(map, key);
if (l) return this_cpu_ptr(htab_elem_get_ptr(l, map->key_size)); else return NULL;}
/* inline bpf_map_lookup_elem() call for per-CPU hashmap */static int htab_percpu_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf){ struct bpf_insn *insn = insn_buf;
if (!bpf_jit_supports_percpu_insn()) return -EOPNOTSUPP;
BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem, (void *(*)(struct bpf_map *map, void *key))NULL)); *insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem); *insn++ = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 3); *insn++ = BPF_ALU64_IMM(BPF_ADD, BPF_REG_0, offsetof(struct htab_elem, key) + roundup(map->key_size, 8)); *insn++ = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0); *insn++ = BPF_MOV64_PERCPU_REG(BPF_REG_0, BPF_REG_0);
return insn - insn_buf;}
static void *htab_percpu_map_lookup_percpu_elem(struct bpf_map *map, void *key, u32 cpu){ struct htab_elem *l;
if (cpu >= nr_cpu_ids) return NULL;
l = __htab_map_lookup_elem(map, key); if (l) return per_cpu_ptr(htab_elem_get_ptr(l, map->key_size), cpu); else return NULL;}
static void *htab_lru_percpu_map_lookup_elem(struct bpf_map *map, void *key){ struct htab_elem *l = __htab_map_lookup_elem(map, key);
if (l) { bpf_lru_node_set_ref(&l->lru_node); return this_cpu_ptr(htab_elem_get_ptr(l, map->key_size)); }
return NULL;}
static void *htab_lru_percpu_map_lookup_percpu_elem(struct bpf_map *map, void *key, u32 cpu){ struct htab_elem *l;
if (cpu >= nr_cpu_ids) return NULL;
l = __htab_map_lookup_elem(map, key); if (l) { bpf_lru_node_set_ref(&l->lru_node); return per_cpu_ptr(htab_elem_get_ptr(l, map->key_size), cpu); }
return NULL;}
int bpf_percpu_hash_copy(struct bpf_map *map, void *key, void *value, u64 map_flags){ struct htab_elem *l; void __percpu *pptr; int ret = -ENOENT; int cpu, off = 0; u32 size;
/* per_cpu areas are zero-filled and bpf programs can only * access 'value_size' of them, so copying rounded areas * will not leak any kernel data */ size = round_up(map->value_size, 8); rcu_read_lock(); l = __htab_map_lookup_elem(map, key); if (!l) goto out; ret = 0; /* We do not mark LRU map element here in order to not mess up * eviction heuristics when user space does a map walk. */ pptr = htab_elem_get_ptr(l, map->key_size); if (map_flags & BPF_F_CPU) { cpu = map_flags >> 32; copy_map_value(map, value, per_cpu_ptr(pptr, cpu)); check_and_init_map_value(map, value); goto out; } for_each_possible_cpu(cpu) { copy_map_value_long(map, value + off, per_cpu_ptr(pptr, cpu)); check_and_init_map_value(map, value + off); off += size; }out: rcu_read_unlock(); return ret;}
int bpf_percpu_hash_update(struct bpf_map *map, void *key, void *value, u64 map_flags){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); int ret;
rcu_read_lock(); if (htab_is_lru(htab)) ret = __htab_lru_percpu_map_update_elem(map, key, value, map_flags, true); else ret = htab_map_update_elem_in_place(map, key, value, map_flags, true, true); rcu_read_unlock();
return ret;}
static void htab_percpu_map_seq_show_elem(struct bpf_map *map, void *key, struct seq_file *m){ struct htab_elem *l; void __percpu *pptr; int cpu;
rcu_read_lock();
l = __htab_map_lookup_elem(map, key); if (!l) { rcu_read_unlock(); return; }
btf_type_seq_show(map->btf, map->btf_key_type_id, key, m); seq_puts(m, ": {\n"); pptr = htab_elem_get_ptr(l, map->key_size); for_each_possible_cpu(cpu) { seq_printf(m, "\tcpu%d: ", cpu); btf_type_seq_show(map->btf, map->btf_value_type_id, per_cpu_ptr(pptr, cpu), m); seq_putc(m, '\n'); } seq_puts(m, "}\n");
rcu_read_unlock();}
const struct bpf_map_ops htab_percpu_map_ops = { .map_meta_equal = bpf_map_meta_equal, .map_alloc_check = htab_map_alloc_check, .map_alloc = htab_map_alloc, .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_percpu_map_lookup_elem, .map_gen_lookup = htab_percpu_map_gen_lookup, .map_lookup_and_delete_elem = htab_percpu_map_lookup_and_delete_elem, .map_update_elem = htab_percpu_map_update_elem, .map_delete_elem = htab_map_delete_elem, .map_lookup_percpu_elem = htab_percpu_map_lookup_percpu_elem, .map_seq_show_elem = htab_percpu_map_seq_show_elem, .map_set_for_each_callback_args = map_set_for_each_callback_args, .map_for_each_callback = bpf_for_each_hash_elem, .map_check_btf = htab_map_check_btf, .map_mem_usage = htab_map_mem_usage, BATCH_OPS(htab_percpu), .map_btf_id = &htab_map_btf_ids[0], .iter_seq_info = &iter_seq_info,};
const struct bpf_map_ops htab_lru_percpu_map_ops = { .map_meta_equal = bpf_map_meta_equal, .map_alloc_check = htab_map_alloc_check, .map_alloc = htab_map_alloc, .map_free = htab_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_lru_percpu_map_lookup_elem, .map_lookup_and_delete_elem = htab_lru_percpu_map_lookup_and_delete_elem, .map_update_elem = htab_lru_percpu_map_update_elem, .map_delete_elem = htab_lru_map_delete_elem, .map_lookup_percpu_elem = htab_lru_percpu_map_lookup_percpu_elem, .map_seq_show_elem = htab_percpu_map_seq_show_elem, .map_set_for_each_callback_args = map_set_for_each_callback_args, .map_for_each_callback = bpf_for_each_hash_elem, .map_check_btf = htab_map_check_btf, .map_mem_usage = htab_map_mem_usage, BATCH_OPS(htab_lru_percpu), .map_btf_id = &htab_map_btf_ids[0], .iter_seq_info = &iter_seq_info,};
static int fd_htab_map_alloc_check(union bpf_attr *attr){ if (attr->value_size != sizeof(u32)) return -EINVAL; return htab_map_alloc_check(attr);}
static void fd_htab_map_free(struct bpf_map *map){ struct bpf_htab *htab = container_of(map, struct bpf_htab, map); struct hlist_nulls_node *n; struct hlist_nulls_head *head; struct htab_elem *l; int i;
for (i = 0; i < htab->n_buckets; i++) { head = select_bucket(htab, i);
hlist_nulls_for_each_entry_safe(l, n, head, hash_node) { void *ptr = fd_htab_map_get_ptr(map, l);
map->ops->map_fd_put_ptr(map, ptr, false); } }
htab_map_free(map);}
/* only called from syscall */int bpf_fd_htab_map_lookup_elem(struct bpf_map *map, void *key, u32 *value){ void **ptr; int ret = 0;
if (!map->ops->map_fd_sys_lookup_elem) return -ENOTSUPP;
rcu_read_lock(); ptr = htab_map_lookup_elem(map, key); if (ptr) *value = map->ops->map_fd_sys_lookup_elem(READ_ONCE(*ptr)); else ret = -ENOENT; rcu_read_unlock();
return ret;}
/* Only called from syscall */int bpf_fd_htab_map_update_elem(struct bpf_map *map, struct file *map_file, void *key, void *value, u64 map_flags){ void *ptr; int ret;
ptr = map->ops->map_fd_get_ptr(map, map_file, *(int *)value); if (IS_ERR(ptr)) return PTR_ERR(ptr);
/* The htab bucket lock is always held during update operations in fd * htab map, and the following rcu_read_lock() is only used to avoid * the WARN_ON_ONCE in htab_map_update_elem_in_place(). */ rcu_read_lock(); ret = htab_map_update_elem_in_place(map, key, &ptr, map_flags, false, false); rcu_read_unlock(); if (ret) map->ops->map_fd_put_ptr(map, ptr, false);
return ret;}
static struct bpf_map *htab_of_map_alloc(union bpf_attr *attr){ struct bpf_map *map, *inner_map_meta;
inner_map_meta = bpf_map_meta_alloc(attr->inner_map_fd); if (IS_ERR(inner_map_meta)) return inner_map_meta;
map = htab_map_alloc(attr); if (IS_ERR(map)) { bpf_map_meta_free(inner_map_meta); return map; }
map->inner_map_meta = inner_map_meta;
return map;}
static void *htab_of_map_lookup_elem(struct bpf_map *map, void *key){ struct bpf_map **inner_map = htab_map_lookup_elem(map, key);
if (!inner_map) return NULL;
return READ_ONCE(*inner_map);}
static int htab_of_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf){ struct bpf_insn *insn = insn_buf; const int ret = BPF_REG_0;
BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem, (void *(*)(struct bpf_map *map, void *key))NULL)); *insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem); *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 2); *insn++ = BPF_ALU64_IMM(BPF_ADD, ret, offsetof(struct htab_elem, key) + round_up(map->key_size, 8)); *insn++ = BPF_LDX_MEM(BPF_DW, ret, ret, 0);
return insn - insn_buf;}
static void htab_of_map_free(struct bpf_map *map){ bpf_map_meta_free(map->inner_map_meta); fd_htab_map_free(map);}
const struct bpf_map_ops htab_of_maps_map_ops = { .map_alloc_check = fd_htab_map_alloc_check, .map_alloc = htab_of_map_alloc, .map_free = htab_of_map_free, .map_get_next_key = htab_map_get_next_key, .map_lookup_elem = htab_of_map_lookup_elem, .map_delete_elem = htab_map_delete_elem, .map_fd_get_ptr = bpf_map_fd_get_ptr, .map_fd_put_ptr = bpf_map_fd_put_ptr, .map_fd_sys_lookup_elem = bpf_map_fd_sys_lookup_elem, .map_gen_lookup = htab_of_map_gen_lookup, .map_check_btf = map_check_no_btf, .map_mem_usage = htab_map_mem_usage, BATCH_OPS(htab), .map_btf_id = &htab_map_btf_ids[0],};
struct rhtab_elem { struct rhash_head node; /* key bytes, then value bytes follow */ u8 data[] __aligned(8);};
struct bpf_rhtab { struct bpf_map map; struct rhashtable ht; struct bpf_mem_alloc ma; u32 elem_size; bool freeing_internal;};
static const struct rhashtable_params rhtab_params = { .head_offset = offsetof(struct rhtab_elem, node), .key_offset = offsetof(struct rhtab_elem, data),};
static inline void *rhtab_elem_value(struct rhtab_elem *l, u32 key_size){ return l->data + round_up(key_size, 8);}
/* Specialize hash function and objcmp for long sized key */static __always_inline int rhtab_key_cmp_long(struct rhashtable_compare_arg *arg, const void *ptr){ const unsigned long key1 = *(const unsigned long *)arg->key; const struct rhtab_elem *key2 = ptr;
return key1 != *(const unsigned long *)key2->data;}
static __always_inline u32 rhtab_hashfn_long(const void *data, u32 len, u32 seed){ u64 k = *(const unsigned long *)data;
return (u32)(k ^ (k >> 32)) ^ seed;}
static const struct rhashtable_params rhtab_params_long = { .head_offset = offsetof(struct rhtab_elem, node), .key_offset = offsetof(struct rhtab_elem, data), .key_len = sizeof(long), .hashfn = rhtab_hashfn_long, .obj_cmpfn = rhtab_key_cmp_long,};
static struct bpf_map *rhtab_map_alloc(union bpf_attr *attr){ struct rhashtable_params params; struct bpf_rhtab *rhtab; int err = 0;
rhtab = bpf_map_area_alloc(sizeof(*rhtab), NUMA_NO_NODE); if (!rhtab) return ERR_PTR(-ENOMEM);
bpf_map_init_from_attr(&rhtab->map, attr);
if (rhtab->map.max_entries > 1UL << 31) { err = -E2BIG; goto free_rhtab; }
rhtab->elem_size = sizeof(struct rhtab_elem) + round_up(rhtab->map.key_size, 8) + round_up(rhtab->map.value_size, 8);
params = rhtab_params; params.key_len = rhtab->map.key_size; params.nelem_hint = (u32)attr->map_extra; params.automatic_shrinking = true;
if (rhtab->map.key_size == sizeof(long)) { params.hashfn = rhtab_hashfn_long; params.obj_cmpfn = rhtab_key_cmp_long; }
err = rhashtable_init(&rhtab->ht, ¶ms); if (err) goto free_rhtab;
/* Set max_elems after rhashtable_init() since init zeroes the struct */ rhtab->ht.max_elems = rhtab->map.max_entries;
err = bpf_mem_alloc_init(&rhtab->ma, rhtab->elem_size, false); if (err) goto destroy_rhtab;
return &rhtab->map;
destroy_rhtab: rhashtable_destroy(&rhtab->ht);free_rhtab: bpf_map_area_free(rhtab); return ERR_PTR(err);}
static int rhtab_map_alloc_check(union bpf_attr *attr){ if (!(attr->map_flags & BPF_F_NO_PREALLOC)) return -EINVAL;
if (attr->map_flags & BPF_F_ZERO_SEED) return -EINVAL;
if (attr->key_size > U16_MAX) return -E2BIG;
if (attr->map_extra >> 32) return -EINVAL;
if ((u32)attr->map_extra > U16_MAX) return -E2BIG;
if ((u32)attr->map_extra > attr->max_entries) return -EINVAL;
return htab_map_alloc_check(attr);}
static void rhtab_check_and_free_fields(struct bpf_rhtab *rhtab, struct rhtab_elem *elem){ if (IS_ERR_OR_NULL(rhtab->map.record)) return;
bpf_obj_free_fields(rhtab->map.record, rhtab_elem_value(elem, rhtab->map.key_size));}
static void rhtab_mem_dtor(void *obj, void *ctx){ struct htab_btf_record *hrec = ctx; struct rhtab_elem *elem = obj;
if (IS_ERR_OR_NULL(hrec->record)) return;
bpf_obj_free_fields(hrec->record, rhtab_elem_value(elem, hrec->key_size));}
static void rhtab_free_elem(void *ptr, void *arg){ struct bpf_rhtab *rhtab = arg; struct rhtab_elem *elem = ptr;
bpf_map_free_internal_structs(&rhtab->map, rhtab_elem_value(elem, rhtab->map.key_size)); bpf_mem_cache_free_rcu(&rhtab->ma, elem);}
static void rhtab_map_free(struct bpf_map *map){ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
rhashtable_free_and_destroy(&rhtab->ht, rhtab_free_elem, rhtab); bpf_mem_alloc_destroy(&rhtab->ma); bpf_map_area_free(rhtab);}
static void *rhtab_lookup_elem(struct bpf_map *map, void *key){ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
/* Hold RCU lock in case sleepable program calls via gen_lookup */ guard(rcu)();
if (map->key_size == sizeof(long)) return rhashtable_lookup_likely(&rhtab->ht, key, rhtab_params_long);
return rhashtable_lookup_likely(&rhtab->ht, key, rhtab_params);}
static void *rhtab_map_lookup_elem(struct bpf_map *map, void *key) __must_hold(RCU){ struct rhtab_elem *l;
l = rhtab_lookup_elem(map, key); return l ? rhtab_elem_value(l, map->key_size) : NULL;}
static void rhtab_read_elem_value(struct bpf_map *map, void *dst, struct rhtab_elem *elem, u64 flags){ void *src = rhtab_elem_value(elem, map->key_size);
if (flags & BPF_F_LOCK) copy_map_value_locked(map, dst, src, true); else copy_map_value(map, dst, src);}
static int rhtab_delete_elem(struct bpf_rhtab *rhtab, struct rhtab_elem *elem, void *copy, u64 flags){ int err;
/* * disable_instrumentation() mitigates the deadlock for programs running in NMI context. * rhashtable locks bucket with local_irq_save(). Only NMI programs may reenter * rhashtable code, bpf_disable_instrumentation() disables programs running in NMI, except * raw tracepoints, which we don't have in rhashtable. */ bpf_disable_instrumentation();
if (rhtab->map.key_size == sizeof(long)) err = rhashtable_remove_fast(&rhtab->ht, &elem->node, rhtab_params_long); else err = rhashtable_remove_fast(&rhtab->ht, &elem->node, rhtab_params);
bpf_enable_instrumentation();
if (err) return err;
if (copy) { rhtab_read_elem_value(&rhtab->map, copy, elem, flags); check_and_init_map_value(&rhtab->map, copy); } /* Release internal structs: kptr, bpf_timer, task_work, wq */ rhtab_check_and_free_fields(rhtab, elem); bpf_mem_cache_free_rcu(&rhtab->ma, elem); return 0;}
static long rhtab_map_delete_elem(struct bpf_map *map, void *key){ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); struct rhtab_elem *elem;
guard(rcu)();
elem = rhtab_lookup_elem(map, key); if (!elem) return -ENOENT;
return rhtab_delete_elem(rhtab, elem, NULL, 0);}
static int rhtab_map_lookup_and_delete_elem(struct bpf_map *map, void *key, void *value, u64 flags){ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); struct rhtab_elem *elem; int err;
err = bpf_map_check_op_flags(map, flags, BPF_F_LOCK); if (err) return err;
guard(rcu)();
elem = rhtab_lookup_elem(map, key); if (!elem) return -ENOENT;
return rhtab_delete_elem(rhtab, elem, value, flags);}
static long rhtab_map_update_existing(struct bpf_map *map, struct rhtab_elem *elem, void *value, u64 map_flags){ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); void *old_val = rhtab_elem_value(elem, map->key_size);
if (map_flags & BPF_NOEXIST) return -EEXIST;
if (map_flags & BPF_F_LOCK) copy_map_value_locked(map, old_val, value, false); else copy_map_value(map, old_val, value);
/* * Torn reads: a concurrent reader without BPF_F_LOCK may observe * the value mid-copy. Callers requiring consistent reads must use * BPF_F_LOCK, matching arraymap semantics. * * copy_map_value() skips special-field offsets, so old timers/ * kptrs/etc. still sit in the slot. Cancel them after the copy * to match arraymap's update semantics. */ rhtab_check_and_free_fields(rhtab, elem); return 0;}
static long rhtab_map_update_elem(struct bpf_map *map, void *key, void *value, u64 map_flags){ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); struct rhtab_elem *elem, *tmp;
if (unlikely((map_flags & ~BPF_F_LOCK) > BPF_EXIST)) return -EINVAL;
if ((map_flags & BPF_F_LOCK) && !btf_record_has_field(map->record, BPF_SPIN_LOCK)) return -EINVAL;
guard(rcu)(); elem = rhtab_lookup_elem(map, key); if (elem) return rhtab_map_update_existing(map, elem, value, map_flags);
if (map_flags & BPF_EXIST) return -ENOENT;
/* * Reject new insertions while map_release_uref cleanup walks the * table. Without this, new elements could keep triggering rehash * and prevent the walk from terminating. */ if (READ_ONCE(rhtab->freeing_internal)) return -EBUSY;
/* Check max_entries limit before inserting new element */ if (atomic_read(&rhtab->ht.nelems) >= map->max_entries) return -E2BIG;
elem = bpf_mem_cache_alloc(&rhtab->ma); if (!elem) return -ENOMEM;
memcpy(elem->data, key, map->key_size); copy_map_value(map, rhtab_elem_value(elem, map->key_size), value); check_and_init_map_value(map, rhtab_elem_value(elem, map->key_size));
/* Prevent deadlock for NMI programs attempting to take bucket lock */ bpf_disable_instrumentation();
if (map->key_size == sizeof(long)) tmp = rhashtable_lookup_get_insert_fast(&rhtab->ht, &elem->node, rhtab_params_long); else tmp = rhashtable_lookup_get_insert_fast(&rhtab->ht, &elem->node, rhtab_params);
bpf_enable_instrumentation();
if (tmp) { bpf_mem_cache_free(&rhtab->ma, elem); if (IS_ERR(tmp)) return PTR_ERR(tmp);
return rhtab_map_update_existing(map, tmp, value, map_flags); }
return 0;}
static int rhtab_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf){ struct bpf_insn *insn = insn_buf; const int ret = BPF_REG_0;
BUILD_BUG_ON(!__same_type(&rhtab_lookup_elem, (void *(*)(struct bpf_map *map, void *key)) NULL)); *insn++ = BPF_EMIT_CALL(rhtab_lookup_elem); *insn++ = BPF_JMP_IMM(BPF_JEQ, ret, 0, 1); *insn++ = BPF_ALU64_IMM(BPF_ADD, ret, offsetof(struct rhtab_elem, data) + round_up(map->key_size, 8));
return insn - insn_buf;}
static int rhtab_map_check_btf(struct bpf_map *map, const struct btf *btf, const struct btf_type *key_type, const struct btf_type *value_type){ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map);
return bpf_ma_set_dtor(map, &rhtab->ma, rhtab_mem_dtor);}
static void rhtab_map_free_internal_structs(struct bpf_map *map){ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); struct rhashtable_iter iter; struct rhtab_elem *elem;
if (!bpf_map_has_internal_structs(map)) return;
/* * Block new insertions. Once observed, no new growth is triggered, * so any in-flight rehash will drain and the walker is guaranteed * to stop returning -EAGAIN. Treat -EAGAIN as "rehash in progress, * retry"; do not wait for the worker. */ WRITE_ONCE(rhtab->freeing_internal, true);
rhashtable_walk_enter(&rhtab->ht, &iter); rhashtable_walk_start(&iter);
while ((elem = rhashtable_walk_next(&iter))) { if (IS_ERR(elem)) { if (PTR_ERR(elem) == -EAGAIN) continue; break; }
bpf_map_free_internal_structs(map, rhtab_elem_value(elem, map->key_size));
if (need_resched()) { /* Avoid stalls on large maps */ rhashtable_walk_stop(&iter); cond_resched(); rhashtable_walk_start(&iter); } }
rhashtable_walk_stop(&iter); rhashtable_walk_exit(&iter); WRITE_ONCE(rhtab->freeing_internal, false);}
static int rhtab_map_get_next_key(struct bpf_map *map, void *key, void *next_key) __must_hold_shared(RCU){ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); struct rhtab_elem *elem;
elem = rhashtable_next_key(&rhtab->ht, key);
/* if not found, return the first key */ if (PTR_ERR(elem) == -ENOENT) elem = rhashtable_next_key(&rhtab->ht, NULL);
if (IS_ERR(elem)) return PTR_ERR(elem); if (!elem) return -ENOENT;
memcpy(next_key, elem->data, map->key_size); return 0;}
static void rhtab_map_seq_show_elem(struct bpf_map *map, void *key, struct seq_file *m){ void *value;
/* Guarantee that hashtab value is not freed */ guard(rcu)();
value = rhtab_map_lookup_elem(map, key); if (!value) return;
btf_type_seq_show(map->btf, map->btf_key_type_id, key, m); seq_puts(m, ": "); btf_type_seq_show(map->btf, map->btf_value_type_id, value, m); seq_putc(m, '\n');}
static long bpf_each_rhash_elem(struct bpf_map *map, bpf_callback_t callback_fn, void *callback_ctx, u64 flags){ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); void *prev_key = NULL; struct rhtab_elem *elem; int num_elems = 0; u64 ret = 0;
cant_migrate();
if (flags != 0) return -EINVAL;
rcu_read_lock(); /* * Best-effort iteration: if rhashtable is concurrently resized or * elements are deleted/inserted, there may be missed or duplicate * elements visited. */ while ((elem = rhashtable_next_key(&rhtab->ht, prev_key))) { if (IS_ERR(elem)) break; num_elems++; ret = callback_fn((u64)(long)map, (u64)(long)elem->data, (u64)(long)rhtab_elem_value(elem, map->key_size), (u64)(long)callback_ctx, 0); if (ret) break;
prev_key = elem->data; /* valid while RCU held */ } rcu_read_unlock();
return num_elems;}
static u64 rhtab_map_mem_usage(const struct bpf_map *map){ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); u64 num_entries;
/* Excludes rhashtable bucket overhead (~ nelems * sizeof(void *) at 75% load). */ num_entries = atomic_read(&rhtab->ht.nelems); return sizeof(struct bpf_rhtab) + rhtab->elem_size * num_entries;}
static int __rhtab_map_lookup_and_delete_batch(struct bpf_map *map, const union bpf_attr *attr, union bpf_attr __user *uattr, bool do_delete){ struct bpf_rhtab *rhtab = container_of(map, struct bpf_rhtab, map); void __user *uvalues = u64_to_user_ptr(attr->batch.values); void __user *ukeys = u64_to_user_ptr(attr->batch.keys); void __user *ubatch = u64_to_user_ptr(attr->batch.in_batch); void *cursor = NULL, *keys = NULL, *values = NULL, *dst_key, *dst_val; struct rhtab_elem **del_elems = NULL; u32 max_count, total, key_size, value_size, i; bool has_next_cursor = false; struct rhtab_elem *elem; u64 elem_map_flags, map_flags; int ret = 0;
elem_map_flags = attr->batch.elem_flags; ret = bpf_map_check_op_flags(map, elem_map_flags, BPF_F_LOCK); if (ret) return ret;
map_flags = attr->batch.flags; if (map_flags) return -EINVAL;
max_count = attr->batch.count; if (!max_count) return 0;
if (put_user(0, &uattr->batch.count)) return -EFAULT;
key_size = map->key_size; value_size = map->value_size;
keys = kvmalloc_array(max_count, key_size, GFP_USER | __GFP_NOWARN); values = kvmalloc_array(max_count, value_size, GFP_USER | __GFP_NOWARN); if (do_delete) del_elems = kvmalloc_array(max_count, sizeof(void *), GFP_USER | __GFP_NOWARN); cursor = kmalloc(key_size, GFP_USER | __GFP_NOWARN);
if (!keys || !values || !cursor || (do_delete && !del_elems)) { ret = -ENOMEM; goto free; }
if (ubatch && copy_from_user(cursor, ubatch, key_size)) { ret = -EFAULT; goto free; }
dst_key = keys; dst_val = values; total = 0;
rcu_read_lock();
/* * Cursor stores the key of the next-to-process element (stashed by * the previous batch). Look it up directly so the element is included * here rather than skipped by next_key(). If the cursor was deleted * concurrently (or by the previous do_delete batch), return -EAGAIN * so userspace can distinguish a lost cursor from end-of-iteration * (-ENOENT) and restart from a NULL cursor. */ if (ubatch) { elem = rhtab_lookup_elem(map, cursor); if (!elem) { rcu_read_unlock(); ret = -EAGAIN; goto free; } } else { elem = rhashtable_next_key(&rhtab->ht, NULL); }
while (elem && !IS_ERR(elem) && total < max_count) { memcpy(dst_key, elem->data, key_size); rhtab_read_elem_value(map, dst_val, elem, elem_map_flags); check_and_init_map_value(map, dst_val);
if (do_delete) del_elems[total] = elem;
elem = rhashtable_next_key(&rhtab->ht, dst_key); dst_key += key_size; dst_val += value_size; total++;
/* Bail to userspace to avoid stalls. */ if (need_resched()) break; }
if (elem && !IS_ERR(elem)) { /* Stash next-to-process key as cursor for the next batch. */ memcpy(cursor, elem->data, key_size); has_next_cursor = true; }
if (do_delete) { for (i = 0; i < total; i++) rhtab_delete_elem(rhtab, del_elems[i], NULL, 0); }
rcu_read_unlock();
if (total == 0) { ret = -ENOENT; goto free; }
/* No more elements after this batch. */ if (!has_next_cursor) ret = -ENOENT;
if (copy_to_user(ukeys, keys, (size_t)total * key_size) || copy_to_user(uvalues, values, (size_t)total * value_size) || put_user(total, &uattr->batch.count) || (has_next_cursor && copy_to_user(u64_to_user_ptr(attr->batch.out_batch), cursor, key_size))) { ret = -EFAULT; goto free; }
free: kfree(cursor); kvfree(keys); kvfree(values); kvfree(del_elems); return ret;}
static int rhtab_map_lookup_batch(struct bpf_map *map, const union bpf_attr *attr, union bpf_attr __user *uattr){ return __rhtab_map_lookup_and_delete_batch(map, attr, uattr, false);}
static int rhtab_map_lookup_and_delete_batch(struct bpf_map *map, const union bpf_attr *attr, union bpf_attr __user *uattr){ return __rhtab_map_lookup_and_delete_batch(map, attr, uattr, true);}
struct bpf_iter_seq_rhash_map_info { struct bpf_map *map; struct bpf_rhtab *rhtab; struct rhashtable_iter iter;};
static void *bpf_rhash_map_seq_start(struct seq_file *seq, loff_t *pos) __acquires(RCU){ struct bpf_iter_seq_rhash_map_info *info = seq->private; struct rhtab_elem *elem;
rhashtable_walk_start(&info->iter); /* * Re-deliver the element returned by walk_next() at the end of the * previous read() — bpf_seq_read may have stopped before show() * consumed it. Rehash rewinds the walker; retry on -EAGAIN. */ do { elem = rhashtable_walk_peek(&info->iter); } while (PTR_ERR(elem) == -EAGAIN);
if (IS_ERR(elem)) return NULL;
if (elem && *pos == 0) ++*pos; return elem;}
static void *bpf_rhash_map_seq_next(struct seq_file *seq, void *v, loff_t *pos){ struct bpf_iter_seq_rhash_map_info *info = seq->private; struct rhtab_elem *elem;
++*pos;
/* Rehash rewinds the walker; retry until it stops returning -EAGAIN. */ do { elem = rhashtable_walk_next(&info->iter); } while (PTR_ERR(elem) == -EAGAIN);
if (IS_ERR(elem)) return NULL; return elem;}
static int __bpf_rhash_map_seq_show(struct seq_file *seq, struct rhtab_elem *elem){ struct bpf_iter_seq_rhash_map_info *info = seq->private; struct bpf_iter__bpf_map_elem ctx = {}; struct bpf_iter_meta meta; struct bpf_prog *prog; int ret = 0;
meta.seq = seq; prog = bpf_iter_get_info(&meta, elem == NULL); if (prog) { ctx.meta = &meta; ctx.map = info->map; if (elem) { ctx.key = elem->data; ctx.value = rhtab_elem_value(elem, info->map->key_size); } ret = bpf_iter_run_prog(prog, &ctx); }
return ret;}
static int bpf_rhash_map_seq_show(struct seq_file *seq, void *v){ return __bpf_rhash_map_seq_show(seq, v);}
static void bpf_rhash_map_seq_stop(struct seq_file *seq, void *v) __releases(RCU){ struct bpf_iter_seq_rhash_map_info *info = seq->private;
if (!v) (void)__bpf_rhash_map_seq_show(seq, NULL);
rhashtable_walk_stop(&info->iter);}
static int bpf_iter_init_rhash_map(void *priv_data, struct bpf_iter_aux_info *aux){ struct bpf_iter_seq_rhash_map_info *info = priv_data; struct bpf_map *map = aux->map;
bpf_map_inc_with_uref(map); info->map = map; info->rhtab = container_of(map, struct bpf_rhtab, map); rhashtable_walk_enter(&info->rhtab->ht, &info->iter); return 0;}
static void bpf_iter_fini_rhash_map(void *priv_data){ struct bpf_iter_seq_rhash_map_info *info = priv_data;
rhashtable_walk_exit(&info->iter); bpf_map_put_with_uref(info->map);}
static const struct seq_operations bpf_rhash_map_seq_ops = { .start = bpf_rhash_map_seq_start, .next = bpf_rhash_map_seq_next, .stop = bpf_rhash_map_seq_stop, .show = bpf_rhash_map_seq_show,};
static const struct bpf_iter_seq_info rhash_iter_seq_info = { .seq_ops = &bpf_rhash_map_seq_ops, .init_seq_private = bpf_iter_init_rhash_map, .fini_seq_private = bpf_iter_fini_rhash_map, .seq_priv_size = sizeof(struct bpf_iter_seq_rhash_map_info),};
BTF_ID_LIST_SINGLE(rhtab_map_btf_ids, struct, bpf_rhtab)const struct bpf_map_ops rhtab_map_ops = { .map_meta_equal = bpf_map_meta_equal, .map_alloc_check = rhtab_map_alloc_check, .map_alloc = rhtab_map_alloc, .map_free = rhtab_map_free, .map_get_next_key = rhtab_map_get_next_key, .map_release_uref = rhtab_map_free_internal_structs, .map_check_btf = rhtab_map_check_btf, .map_lookup_elem = rhtab_map_lookup_elem, .map_lookup_and_delete_elem = rhtab_map_lookup_and_delete_elem, .map_update_elem = rhtab_map_update_elem, .map_delete_elem = rhtab_map_delete_elem, .map_gen_lookup = rhtab_map_gen_lookup, .map_seq_show_elem = rhtab_map_seq_show_elem, .map_set_for_each_callback_args = map_set_for_each_callback_args, .map_for_each_callback = bpf_each_rhash_elem, .map_mem_usage = rhtab_map_mem_usage, BATCH_OPS(rhtab), .map_btf_id = &rhtab_map_btf_ids[0], .iter_seq_info = &rhash_iter_seq_info,};