1# 内核数据结构 2 3  内核中实现了常用的几种数据结构，这里是他们的api文档。 4 5-------------- 6## kfifo先进先出缓冲区 7 8  kfifo先进先出缓冲区定义于`common/kfifo.h`中。您可以使用它，创建指定大小的fifo缓冲区（最大大小为4GB） 9 10### kfifo_alloc 11 12`int kfifo_alloc(struct kfifo_t *fifo, uint32_t size, uint64_t reserved)` 13 14#### 描述 15 16  通过动态方式初始化kfifo缓冲队列。fifo缓冲区的buffer将由该函数进行申请。 17 18#### 参数 19 20**fifo** 21 22  kfifo队列结构体的指针 23 24**size** 25 26  缓冲区大小（单位：bytes） 27 28**reserved** 29 30  当前字段保留，请将其置为0 31 32#### 返回值 33 34  当返回值为0时，表示正常初始化成功，否则返回对应的errno 35 36### kfifo_init 37 38`void kfifo_init(struct kfifo_t *fifo, void *buffer, uint32_t size)` 39 40#### 描述 41 42  使用指定的缓冲区来初始化kfifo缓冲队列 43 44#### 参数 45 46**fifo** 47 48  kfifo队列结构体的指针 49 50**buffer** 51 52  缓冲区基地址指针 53 54**size** 55 56  缓冲区大小（单位：bytes） 57 58### kfifo_free_alloc 59 60`void kfifo_free_alloc(struct kfifo_t* fifo)` 61 62#### 描述 63 64  释放通过kfifo_alloc创建的fifo缓冲区. 请勿通过该函数释放其他方式创建的kfifo缓冲区。 65 66#### 参数 67 68**fifo** 69 70  kfifo队列结构体的指针 71 72### kfifo_in 73 74`uint32_t kfifo_in(struct kfifo_t *fifo, const void *from, uint32_t size)` 75 76#### 描述 77 78  向kfifo缓冲区推入指定大小的数据。当队列中空间不足时，则不推入数据。 79 80#### 参数 81 82**fifo** 83 84  kfifo队列结构体的指针 85 86**from** 87 88  源数据基地址指针 89 90**size** 91 92  数据大小（单位：bytes） 93 94#### 返回值 95 96  返回成功被推入的数据的大小。 97 98### kfifo_out 99 100`uint32_t kfifo_out(struct kfifo_t *fifo, void *to, uint32_t size)` 101 102#### 描述 103 104  从kfifo缓冲区取出数据，并从队列中删除数据。当队列中数据量不足时，则不取出。 105 106#### 参数 107 108**fifo** 109 110  kfifo队列结构体的指针 111 112**to** 113 114  目标缓冲区基地址指针 115 116**size** 117 118  数据大小（单位：bytes） 119 120#### 返回值 121 122  返回成功被取出的数据的大小。 123 124### kfifo_out_peek 125 126`uint32_t kfifo_out_peek(struct kfifo_t *fifo, void *to, uint32_t size)` 127 128#### 描述 129 130  从kfifo缓冲区取出数据，但是不从队列中删除数据。当队列中数据量不足时，则不取出。 131 132#### 参数 133 134**fifo** 135 136  kfifo队列结构体的指针 137 138**to** 139 140  目标缓冲区基地址指针 141 142**size** 143 144  数据大小（单位：bytes） 145 146#### 返回值 147 148  返回成功被取出的数据的大小。 149 150### kfifo_reset 151 152`kfifo_reset(fifo)` 153 154#### 描述 155 156  忽略kfifo队列中的所有内容，并把输入和输出偏移量都归零 157 158#### 参数 159 160**fifo** 161 162  kfifo队列结构体的指针 163 164### kfifo_reset_out 165 166`kfifo_reset_out(fifo)` 167 168#### 描述 169 170  忽略kfifo队列中的所有内容，并将输入偏移量赋值给输出偏移量 171 172#### 参数 173 174**fifo** 175 176  kfifo队列结构体的指针 177 178### kfifo_total_size 179 180`kfifo_total_size(fifo)` 181 182#### 描述 183 184  获取kfifo缓冲区的最大大小 185 186#### 参数 187 188**fifo** 189 190  kfifo队列结构体的指针 191 192#### 返回值 193 194  缓冲区最大大小 195 196### kfifo_size 197 198`kfifo_size(fifo)` 199 200#### 描述 201 202  获取kfifo缓冲区当前已使用的大小 203 204#### 参数 205 206**fifo** 207 208  kfifo队列结构体的指针 209 210#### 返回值 211 212  缓冲区当前已使用的大小 213 214### kfifo_empty 215 216`kfifo_empty(fifo)` 217 218#### 描述 219 220  判断kfifo缓冲区当前是否为空 221 222#### 参数 223 224**fifo** 225 226  kfifo队列结构体的指针 227 228#### 返回值 229 230| 情况 | 返回值 | 231| ----------------------- | --- | 232| 空 | 1 | 233| 非空 | 0 | 234 235### kfifo_full 236 237`kfifo_full(fifo)` 238 239#### 描述 240 241  判断kfifo缓冲区当前是否为满 242 243#### 参数 244 245**fifo** 246 247  kfifo队列结构体的指针 248 249#### 返回值 250 251| 情况 | 返回值 | 252| ------| --- | 253| 满 | 1 | 254| 不满 | 0 | 255 256------------------ 257 258## ID Allocation 259 260   ida的主要作用是分配+管理id. 它能分配一个最小的, 未被分配出去的id. 当您需要管理某个数据结构时, 可能需要使用id来区分不同的目标. 这个时候, ida将会是很好的选择. 因为ida的十分高效, 运行常数相对数组更小, 而且提供了基本管理id需要用到的功能, 值得您试一试. 261 262  IDA定义于`idr.h`文件中. 您通过`DECLARE_IDA(my_ida)`来创建一个ida对象, 或者`struct ida my_ida; ida_init(&my_ida);`来初始化一个ida. 263 264### ida_init 265`void ida_init(struct ida *ida_p)` 266 267#### 描述 268 269  通初始化IDA, 你需要保证调用函数之前, ida的free_list为空, 否则会导致内存泄漏. 270#### 参数 271 272**ida_p** 273 274   指向ida的指针 275 276#### 返回值 277 278  无返回值 279 280### ida_preload 281`int ida_preload(struct ida *ida_p, gfp_t gfp_mask)` 282 283#### 描述 284 285  为ida预分配空间.您可以不自行调用, 因为当ida需要空间的时候, 内部会自行使用`kmalloc`函数获取空间. 当然, 设计这个函数的目的是为了让您有更多的选择. 当您提前调用这个函数, 可以避免之后在开辟空间上的时间开销. 286#### 参数 287 288**ida_p** 289 290   指向ida的指针 291 292**gfp_mask** 293 294   保留参数, 目前尚未使用. 295 296#### 返回值 297 298  如果分配成功,将返回0; 否则返回负数错误码, 有可能是内存空间不够. 299 300 301### ida_alloc 302`int ida_alloc(struct ida *ida_p, int *p_id)` 303 304#### 描述 305 306  获取一个空闲ID. 您需要注意, 返回值是成功/错误码. 307#### 参数 308 309**ida_p** 310 311   指向ida的指针 312 313**p_id** 314 315   您需要传入一个int变量的指针, 如果成功分配ID, ID将会存储在该指针所指向的地址. 316 317#### 返回值 318 319  如果分配成功,将返回0; 否则返回负数错误码, 有可能是内存空间不够. 320 321 322### ida_count 323`bool ida_count(struct ida *ida_p, int id)` 324 325#### 描述 326 327  查询一个ID是否被分配. 328#### 参数 329 330**ida_p** 331 332   指向ida的指针 333 334**id** 335 336   您查询该ID是否被分配. 337 338#### 返回值 339 340  如果分配,将返回true; 否则返回false. 341 342 343 344### ida_remove 345`void ida_remove(struct ida *ida_p, int id)` 346 347#### 描述 348 349  删除一个已经分配的ID. 如果该ID不存在, 该函数不会产生异常错误, 因为在检测到该ID不存在的时候, 函数将会自动退出. 350#### 参数 351 352**ida_p** 353 354   指向ida的指针 355 356**id** 357 358   您要删除的id. 359 360#### 返回值 361 362  无返回值. 363 364### ida_destroy 365`void ida_destroy(struct ida *ida_p)` 366 367#### 描述 368 369  释放一个IDA所有的空间, 同时删除ida的所有已经分配的id.(所以您不用担心删除id之后, ida还会占用大量空间.) 370#### 参数 371 372**ida_p** 373 374   指向ida的指针 375 376#### 返回值 377 378  无返回值 379 380### ida_empty 381`void ida_empty(struct ida *ida_p)` 382 383#### 描述 384 385   查询一个ida是否为空 386#### 参数 387 388**ida_p** 389 390   指向ida的指针 391 392#### 返回值 393 394  ida为空则返回true，否则返回false。 395 396 397-------------------- 398 399 400## IDR 401 402   idr是一个基于radix-tree的ID-pointer的数据结构. 该数据结构提供了建id与数据指针绑定的功能, 它的主要功能有以下4个： 4031. 获取一个ID, 并且将该ID与一个指针绑定 4042. 删除一个已分配的ID 4053. 根据ID查找对应的指针 4064. 根据ID使用新的ptr替换旧的ptr 407   您可以使用`DECLARE_idr(my_idr)`来创建一个idr。或者您也可以使用`struct idr my_idr; idr_init(my_idr);`这两句话创建一个idr。 408   至于什么是radix-tree，您可以把他简单理解为一个向上生长的多叉树，在实现中，我们选取了64叉树。 409 410### idr_init 411`void idr_init(struct idr *idp)` 412 413#### 描述 414 415  通初始化IDR, 你需要保证调用函数之前, idr的free_list为空, 否则会导致内存泄漏. 416#### 参数 417 418**idp** 419 420   指向idr的指针 421 422#### 返回值 423 424  无返回值 425 426### idr_preload 427`int idr_preload(struct idr *idp, gfp_t gfp_mask)` 428 429#### 描述 430 431  为idr预分配空间.您可以不自行调用, 因为当idr需要空间的时候, 内部会自行使用`kmalloc`函数获取空间. 当然, 设计这个函数的目的是为了让您有更多的选择. 当您提前调用这个函数, 可以避免之后在开辟空间上的时间开销. 432#### 参数 433 434**idp** 435 436   指向idr的指针 437 438**gfp_mask** 439 440   保留参数, 目前尚未使用. 441 442#### 返回值 443 444  如果分配成功,将返回0; 否则返回负数错误码, 有可能是内存空间不够. 445 446 447### idr_alloc 448`int idr_alloc(struct idr *idp, void *ptr, int *id)` 449 450#### 描述 451 452   获取一个空闲ID. 您需要注意, 返回值是成功/错误码. 453   调用这个函数，需要您保证ptr是非空的，即: `ptr != NULL`, 否则将会影响 `idr_find/idr_find_next/idr_find_next_getid/...`等函数的使用。(具体请看这三个函数的说明，当然，只会影响到您的使用体验，并不会影响到idr内部函数的决策和逻辑) 454#### 参数 455 456**idp** 457 458   指向ida的指针 459 460**ptr** 461 462   指向数据的指针 463 464**id** 465 466   您需要传入一个int变量的指针, 如果成功分配ID, ID将会存储在该指针所指向的地址. 467 468#### 返回值 469 470  如果分配成功,将返回0; 否则返回负数错误码, 有可能是内存空间不够. 471 472 473### idr_remove 474`void* idr_remove(struct idr *idp, int id)` 475 476#### 描述 477 478  删除一个id, 但是不释放对应的ptr指向的空间, 同时返回这个被删除id所对应的ptr。 479   如果该ID不存在, 该函数不会产生异常错误, 因为在检测到该ID不存在的时候, 函数将会自动退出，并返回NULL。 480#### 参数 481 482**idp** 483 484   指向idr的指针 485 486**id** 487 488   您要删除的id. 489 490#### 返回值 491 492  如果删除成功，就返回被删除id所对应的ptr；否则返回NULL。注意：如果这个id本来就和NULL绑定，那么也会返回NULL 493 494 495### idr_remove_all 496`void idr_remove_all(struct idr *idp)` 497 498#### 描述 499 500  删除idr的所有已经分配的id.(所以您不用担心删除id之后, idr还会占用大量空间。) 501 502   但是你需要注意的是，调用这个函数是不会释放数据指针指向的空间的。 所以您调用该函数之前， 确保IDR内部的数据指针被保存。否则当IDR删除所有ID之后， 将会造成内存泄漏。 503 504#### 参数 505 506**idp** 507 508   指向idr的指针 509 510#### 返回值 511 512  无返回值 513 514 515### idr_destroy 516`void idr_destroy(struct idr *idp)` 517 518#### 描述 519 520  释放一个IDR所有的空间, 同时删除idr的所有已经分配的id.(所以您不用担心删除id之后, ida还会占用大量空间.) - 和`idr_remove_all`的区别是， 释放掉所有的空间(包括free_list的预分配空间)。 521#### 参数 522 523**idp** 524 525   指向idr的指针 526 527#### 返回值 528 529  无返回值 530 531 532### idr_find 533`void *idr_find(struct idr *idp, int id)` 534 535#### 描述 536 537  查询一个ID所绑定的数据指针 538#### 参数 539 540**idp** 541 542   指向idr的指针 543 544**id** 545 546   您查询该ID的数据指针 547 548#### 返回值 549 550   如果分配,将返回该ID对应的数据指针; 否则返回NULL.(注意， 返回NULL不一定代表这ID不存在，有可能该ID就是与空指针绑定。) 551   当然，我们也提供了`idr_count`函数来判断id是否被分配，具体请查看idr_count介绍。 552 553### idr_find_next 554`void *idr_find_next(struct idr *idp, int start_id)` 555 556#### 描述 557 558  传进一个start_id，返回满足 "id大于start_id的最小id" 所对应的数据指针。 559#### 参数 560 561**idp** 562 563   指向idr的指针 564 565**start_id** 566 567  您提供的ID限制 568 569#### 返回值 570 571   如果分配,将返回该ID对应的数据指针; 否则返回NULL.(注意， 返回NULL不一定代表这ID不存在，有可能该ID就是与空指针绑定。) 572   当然，我们也提供了`idr_count`函数来判断id是否被分配，具体请查看idr_count介绍。 573 574 575### idr_find_next_getid 576`void *idr_find_next_getid(struct idr *idp, int start_id, int *nextid)` 577 578#### 描述 579 580  传进一个start_id，返回满足 "id大于start_id的最小id" 所对应的数据指针。同时，你获取到这个满足条件的最小id， 即参数中的 *nextid。 581#### 参数 582 583**idp** 584 585   指向idr的指针 586 587**start_id** 588 589   您提供的ID限制 590 591#### 返回值 592 593   如果分配,将返回该ID对应的数据指针; 否则返回NULL.(注意， 返回NULL不一定代表这ID不存在，有可能该ID就是与空指针绑定。) 594   当然，我们也提供了`idr_count`函数来判断id是否被分配，具体请查看idr_count介绍。 595 596 597### idr_replace 598`int idr_replace(struct idr *idp, void *ptr, int id)` 599 600#### 描述 601 602  传进一个ptr，使用该ptr替换掉id所对应的Old_ptr。 603#### 参数 604 605**idp** 606 607   指向idr的指针 608 609**ptr** 610 611  您要替换原来的old_ptr的新指针 612 613**id** 614 615   您要替换的指针所对应的id 616 617#### 返回值 618 619   0代表成功，否则就是错误码 - 代表错误。 620 621 622### idr_replace_get_old 623`int idr_replace_get_old(struct idr *idp, void *ptr, int id, void **oldptr)` 624 625#### 描述 626 627  传进一个ptr，使用该ptr替换掉id所对应的Old_ptr，同时你可以获取到old_ptr。 628#### 参数 629 630**idp** 631 632   指向idr的指针 633 634**ptr** 635 636  您要替换原来的old_ptr的新指针 637 638**id** 639 640   您要替换的指针所对应的id 641 642 643**old_ptr** 644 645   您需要传进该(void**)指针，old_ptr将会存放在该指针所指向的地址。 646 647 648#### 返回值 649 650   0代表成功，否则就是错误码 - 代表错误。 651 652### idr_empty 653`void idr_empty(struct idr *idp)` 654 655#### 描述 656 657   查询一个idr是否为空 658#### 参数 659 660**idp** 661 662   指向idr的指针 663 664#### 返回值 665 666  idr为空则返回true，否则返回false。 667 668### idr_count 669`bool idr_count(struct idr *idp, int id)` 670 671#### 描述 672 673  查询一个ID是否被分配. 674#### 参数 675 676**ida_p** 677 678   指向idr的指针 679 680**id** 681 682   您查询该ID是否被分配. 683 684#### 返回值 685 686  如果分配,将返回true; 否则返回false.