gerrit.fd Code Review - tldk.git/blob - lib/libtle

1 /*

3 * Licensed under the Apache License, Version 2.0 (the "License");

4 * you may not use this file except in compliance with the License.

5 * You may obtain a copy of the License at:

6 *

7 * http://www.apache.org/licenses/LICENSE-2.0

8 *

9 * Unless required by applicable law or agreed to in writing, software

10 * distributed under the License is distributed on an "AS IS" BASIS,

11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

12 * See the License for the specific language governing permissions and

13 * limitations under the License.

14 */

16 #include <tle_memtank.h>

17 #include <rte_errno.h>

18 #include <stdalign.h>

20 struct memobj {

21 struct memchunk *chunk; /* ptr to the chunk it belongs to */

22 uint8_t buf[] __rte_cache_min_aligned; /* memory buffer */

23 } __rte_cache_min_aligned;

25 struct memchunk {

26 TAILQ_ENTRY(memchunk) link; /* link to the next chunk in the tank */

27 void *raw; /* un-aligned ptr returned by alloc() */

28 uint32_t nb_total; /* total number of objects in the chunk */

29 uint32_t nb_free; /* number of free object in the chunk */

30 void *free[]; /* array of free objects */

31 } __rte_cache_aligned;

34 TAILQ_HEAD(mchunk_head, memchunk);

36 struct mchunk_list {

37 rte_spinlock_t lock;

38 struct mchunk_head chunk; /* list of chunks */

39 } __rte_cache_aligned;

41 enum {

42 MC_FULL, /* all memchunk objs are free */

43 MC_USED, /* some of memchunk objs are allocated */

44 MC_NUM,

45 };

47 struct memtank {

48 /* user provided data */

49 struct tle_memtank_prm prm;

51 /*run-time data */

52 void *raw; /* un-aligned ptr returned by alloc() */

53 size_t chunk_size; /* full size of each memchunk */

54 uint32_t obj_size; /* full size of each memobj */

55 rte_atomic32_t nb_chunks; /* number of allocated chunks */

57 struct mchunk_list chl[MC_NUM]; /* lists of memchunks */

59 struct tle_memtank pub;

60 };

62 #define ALIGN_MUL_CEIL(v, mul) \

63 (((v) + (typeof(v))(mul) - 1) / ((typeof(v))(mul)))

65 /*

66 * Obtain pointer to interal memtank struct from public one

67 */

68 static inline struct memtank *

69 tank_pub_full(void *p)

70 {

71 uintptr_t v;

73 v = (uintptr_t)p - offsetof(struct memtank, pub);

74 return (struct memtank *)v;

75 }

77 /*

78 * Obtain pointer to interal memobj struct from public one

79 */

80 static inline struct memobj *

81 obj_pub_full(void *p)

82 {

83 uintptr_t v;

85 v = (uintptr_t)p - offsetof(struct memobj, buf);

86 return (struct memobj *)v;

87 }

89 static inline void *

90 obj_full_pub(struct memobj *obj)

91 {

92 uintptr_t v;

94 v = (uintptr_t)obj + offsetof(struct memobj, buf);

95 return (void *)v;

96 }

98 static inline size_t

99 memtank_meta_size(uint32_t nb_free)

100 {

101 size_t sz;

102 static const struct memtank *mt;

103

104 sz = sizeof(*mt) + nb_free * sizeof(mt->pub.free[0]);

105 sz = RTE_ALIGN_CEIL(sz, alignof(*mt));

106 return sz;

107 }

108

109 static inline size_t

110 memchunk_meta_size(uint32_t nb_obj)

111 {

112 size_t sz;

113 static const struct memchunk *ch;

114

115 sz = sizeof(*ch) + nb_obj * sizeof(ch->free[0]);

116 sz = RTE_ALIGN_CEIL(sz, alignof(*ch));

117 return sz;

118 }

119

120 static inline size_t

121 memobj_size(uint32_t obj_sz)

122 {

123 size_t sz;

124 static const struct memobj *obj;

125

126 sz = sizeof(*obj) + obj_sz;

127 sz = RTE_ALIGN_CEIL(sz, alignof(*obj));

128 return sz;

129 }

130

131 static inline size_t

132 memchunk_size(uint32_t nb_obj, uint32_t obj_sz)

133 {

134 size_t sz;

135

136 sz = memchunk_meta_size(nb_obj);

137 sz += nb_obj * memobj_size(obj_sz);

138 return sz;

139 }

140

141 static void

142 init_chunk(struct memtank *mt, struct memchunk *ch)

143 {

144 uint32_t i, n, sz;

145 struct memobj *obj;

146

147 n = mt->prm.nb_obj_chunk;

148 sz = mt->obj_size;

149

150 /* get start of memobj array */

151 obj = (struct memobj *)((uintptr_t)ch + memchunk_meta_size(n));

152

153 for (i = 0; i != n; i++) {

154 obj->chunk = ch;

155 ch->free[i] = obj_full_pub(obj);

156 obj = (struct memobj *)((uintptr_t)obj + sz);

157 }

158

159 ch->nb_total = n;

160 ch->nb_free = n;

161 }

162

163 static void

164 put_chunk(struct memtank *mt, struct memchunk *ch, void * const obj[],

165 uint32_t num)

166 {

167 uint32_t k, n;

168 struct mchunk_list *ls;

169

170 /* chunk should be in the *used* list */

171 k = MC_USED;

172 ls = &mt->chl[k];

173 rte_spinlock_lock(&ls->lock);

174

175 n = ch->nb_free;

176 RTE_ASSERT(n + num <= ch->nb_total);

177

178 _copy_objs(ch->free, obj, num);

179 ch->nb_free = n + num;

180

181 /* chunk is full now */

182 if (ch->nb_free == ch->nb_total) {

183 TAILQ_REMOVE(&ls->chunk, ch, link);

184 k = MC_FULL;

185 /* chunk is not empty anymore, move it to the head */

186 } else if (n == 0) {

187 TAILQ_REMOVE(&ls->chunk, ch, link);

188 TAILQ_INSERT_HEAD(&ls->chunk, ch, link);

189 }

190

191 rte_spinlock_unlock(&ls->lock);

192

193 /* insert this chunk into the *full* list */

194 if (k == MC_FULL) {

195 ls = &mt->chl[k];

196 rte_spinlock_lock(&ls->lock);

197 TAILQ_INSERT_HEAD(&ls->chunk, ch, link);

198 rte_spinlock_unlock(&ls->lock);

199 }

200 }

201

202 static uint32_t

203 shrink_chunk(struct memtank *mt, uint32_t num)

204 {

205 uint32_t i, k;

206 struct mchunk_list *ls;

207 struct memchunk *ch[num];

208

209 ls = &mt->chl[MC_FULL];

210 rte_spinlock_lock(&ls->lock);

211

212 for (k = 0; k != num; k++) {

213 ch[k] = TAILQ_LAST(&ls->chunk, mchunk_head);

214 if (ch[k] == NULL)

215 break;

216 TAILQ_REMOVE(&ls->chunk, ch[k], link);

217 }

218

219 rte_spinlock_unlock(&ls->lock);

220

221 rte_atomic32_sub(&mt->nb_chunks, k);

222

223 for (i = 0; i != k; i++)

224 mt->prm.free(ch[i]->raw, mt->prm.udata);

225

226 return k;

227 }

228

229 static struct memchunk *

230 alloc_chunk(struct memtank *mt)

231 {

232 size_t sz;

233 void *p;

234 struct memchunk *ch;

235

236 sz = mt->chunk_size + alignof(*ch);

237 p = mt->prm.alloc(sz, mt->prm.udata);

238 if (p == NULL)

239 return NULL;

240 ch = RTE_PTR_ALIGN_CEIL(p, alignof(*ch));

241 ch->raw = p;

242 return ch;

243 }

244

245 /* Determine by how many chunks we can actually grow */

246 static inline uint32_t

247 grow_num(struct memtank *mt, uint32_t num)

248 {

249 uint32_t k, n, max;

250

251 max = mt->prm.max_chunk;

252 n = rte_atomic32_add_return(&mt->nb_chunks, num);

253

254 if (n <= max)

255 return num;

256

257 k = n - max;

258 return (k >= num) ? 0 : num - k;

259 }

260

261 static uint32_t

262 grow_chunk(struct memtank *mt, uint32_t num)

263 {

264 uint32_t i, k, n;

265 struct mchunk_list *fls;

266 struct mchunk_head ls;

267 struct memchunk *ch[num];

268

269 /* check can we grow further */

270 k = grow_num(mt, num);

271

272 for (n = 0; n != k; n++) {

273 ch[n] = alloc_chunk(mt);

274 if (ch[n] == NULL)

275 break;

276 }

277

278 TAILQ_INIT(&ls);

279

280 for (i = 0; i != n; i++) {

281 init_chunk(mt, ch[i]);

282 TAILQ_INSERT_HEAD(&ls, ch[i], link);

283 }

284

285 if (n != 0) {

286 fls = &mt->chl[MC_FULL];

287 rte_spinlock_lock(&fls->lock);

288 TAILQ_CONCAT(&fls->chunk, &ls, link);

289 rte_spinlock_unlock(&fls->lock);

290 }

291

292 if (n != num)

293 rte_atomic32_sub(&mt->nb_chunks, num - n);

294

295 return n;

296 }

297

298

299 void

300 tle_memtank_chunk_free(struct tle_memtank *t, void * const obj[],

301 uint32_t nb_obj, uint32_t flags)

302 {

303 uint32_t i, j, k;

304 struct memtank *mt;

305 struct memobj *mo;

306 struct memchunk *ch[nb_obj];

307

308 mt = tank_pub_full(t);

309

310 for (i = 0; i != nb_obj; i++) {

311 mo = obj_pub_full(obj[i]);

312 ch[i] = mo->chunk;

313 }

314

315 k = 0;

316 for (i = 0; i != nb_obj; i += j) {

317

318 /* find number of consequtive objs from the same chunk */

319 for (j = i + 1; j != nb_obj && ch[j] == ch[i]; j++)

320 ;

321

322 put_chunk(mt, ch[i], obj + i, j - i);

323 k++;

324 }

325

326 if (flags & TLE_MTANK_FREE_SHRINK)

327 shrink_chunk(mt, k);

328 }

329

330 static uint32_t

331 get_chunk(struct mchunk_list *ls, struct mchunk_head *els,

332 struct mchunk_head *uls, void *obj[], uint32_t nb_obj)

333 {

334 uint32_t l, k, n;

335 struct memchunk *ch, *nch;

336

337 rte_spinlock_lock(&ls->lock);

338

339 n = 0;

340 for (ch = TAILQ_FIRST(&ls->chunk);

341 n != nb_obj && ch != NULL && ch->nb_free != 0;

342 ch = nch, n += k) {

343

344 k = RTE_MIN(nb_obj - n, ch->nb_free);

345 l = ch->nb_free - k;

346 _copy_objs(obj + n, ch->free + l, k);

347 ch->nb_free = l;

348

349 nch = TAILQ_NEXT(ch, link);

350

351 /* chunk is empty now */

352 if (l == 0) {

353 TAILQ_REMOVE(&ls->chunk, ch, link);

354 TAILQ_INSERT_TAIL(els, ch, link);

355 } else if (uls != NULL) {

356 TAILQ_REMOVE(&ls->chunk, ch, link);

357 TAILQ_INSERT_HEAD(uls, ch, link);

358 }

359 }

360

361 rte_spinlock_unlock(&ls->lock);

362 return n;

363 }

364

365 uint32_t

366 tle_memtank_chunk_alloc(struct tle_memtank *t, void *obj[], uint32_t nb_obj,

367 uint32_t flags)

368 {

369 uint32_t k, n;

370 struct memtank *mt;

371 struct mchunk_head els, uls;

372

373 mt = tank_pub_full(t);

374

375 /* walk though the the *used* list first */

376 n = get_chunk(&mt->chl[MC_USED], &mt->chl[MC_USED].chunk, NULL,

377 obj, nb_obj);

378

379 if (n != nb_obj) {

380

381 TAILQ_INIT(&els);

382 TAILQ_INIT(&uls);

383

384 /* walk though the the *full* list */

385 n += get_chunk(&mt->chl[MC_FULL], &els, &uls,

386 obj + n, nb_obj - n);

387

388 if (n != nb_obj && (flags & TLE_MTANK_ALLOC_GROW) != 0) {

389

390 /* try to allocate extra memchunks */

391 k = ALIGN_MUL_CEIL(nb_obj - n,

392 mt->prm.nb_obj_chunk);

393 k = grow_chunk(mt, k);

394

395 /* walk through the *full* list again */

396 if (k != 0)

397 n += get_chunk(&mt->chl[MC_FULL], &els, &uls,

398 obj + n, nb_obj - n);

399 }

400

401 /* concatenate with *used* list our temporary lists */

402 rte_spinlock_lock(&mt->chl[MC_USED].lock);

403

404 /* put new non-emtpy elems at head of the *used* list */

405 TAILQ_CONCAT(&uls, &mt->chl[MC_USED].chunk, link);

406 TAILQ_CONCAT(&mt->chl[MC_USED].chunk, &uls, link);

407

408 /* put new emtpy elems at tail of the *used* list */

409 TAILQ_CONCAT(&mt->chl[MC_USED].chunk, &els, link);

410

411 rte_spinlock_unlock(&mt->chl[MC_USED].lock);

412 }

413

414 return n;

415 }

416

417 int

418 tle_memtank_grow(struct tle_memtank *t)

419 {

420 uint32_t k, n, num;

421 struct memtank *mt;

422

423 mt = tank_pub_full(t);

424

425 /* how many chunks we need to grow */

426 k = t->min_free - t->nb_free;

427 if ((int32_t)k <= 0)

428 return 0;

429

430 num = ALIGN_MUL_CEIL(k, mt->prm.nb_obj_chunk);

431

432 /* try to grow and refill the *free* */

433 n = grow_chunk(mt, num);

434 if (n != 0)

435 _fill_free(t, k, 0);

436

437 return n;

438 }

439

440 int

441 tle_memtank_shrink(struct tle_memtank *t)

442 {

443 uint32_t num;

444 struct memtank *mt;

445

446 mt = tank_pub_full(t);

447

448 if (t->nb_free < t->max_free)

449 return 0;

450

451 /* how many chunks we need to free */

452 num = ALIGN_MUL_CEIL(t->min_free, mt->prm.nb_obj_chunk);

453

454 /* free up to *num* chunks */

455 return shrink_chunk(mt, num);

456 }

457

458 static int

459 check_param(const struct tle_memtank_prm *prm)

460 {

461 if (prm->alloc == NULL || prm->free == NULL ||

462 prm->min_free > prm->max_free)

463 return -EINVAL;

464 return 0;

465 }

466

467 struct tle_memtank *

468 tle_memtank_create(const struct tle_memtank_prm *prm)

469 {

470 int32_t rc;

471 size_t sz;

472 void *p;

473 struct memtank *mt;

474

475 rc = check_param(prm);

476 if (rc != 0) {

477 rte_errno = -rc;

478 return NULL;

479 }

480

481 sz = memtank_meta_size(prm->max_free);

482 p = prm->alloc(sz, prm->udata);

483 if (p == NULL) {

484 rte_errno = ENOMEM;

485 return NULL;

486 }

487

488 mt = RTE_PTR_ALIGN_CEIL(p, alignof(*mt));

489

490 memset(mt, 0, sizeof(*mt));

491 mt->prm = *prm;

492

493 mt->raw = p;

494 mt->chunk_size = memchunk_size(prm->nb_obj_chunk, prm->obj_size);

495 mt->obj_size = memobj_size(prm->obj_size);

496

497 mt->pub.min_free = prm->min_free;

498 mt->pub.max_free = prm->max_free;

499

500 TAILQ_INIT(&mt->chl[MC_FULL].chunk);

501 TAILQ_INIT(&mt->chl[MC_USED].chunk);

502

503 return &mt->pub;

504 }

505

506 static void

507 free_mchunk_list(struct memtank *mt, struct mchunk_list *ls)

508 {

509 struct memchunk *ch;

510

511 for (ch = TAILQ_FIRST(&ls->chunk); ch != NULL;

512 ch = TAILQ_FIRST(&ls->chunk)) {

513 TAILQ_REMOVE(&ls->chunk, ch, link);

514 mt->prm.free(ch->raw, mt->prm.udata);

515 }

516 }

517

518 void

519 tle_memtank_destroy(struct tle_memtank *t)

520 {

521 struct memtank *mt;

522

523 mt = tank_pub_full(t);

524 free_mchunk_list(mt, &mt->chl[MC_FULL]);

525 free_mchunk_list(mt, &mt->chl[MC_USED]);

526 mt->prm.free(mt->raw, mt->prm.udata);

527 }