1 /** 2 * @file jbuf.c Jitter Buffer implementation 3 * 4 * Copyright (C) 2010 Creytiv.com 5 */ 6 #include <re_types.h> 7 #include <re_fmt.h> 8 #include <re_list.h> 9 #include <re_mbuf.h> 10 #include <re_mem.h> 11 #include <re_rtp.h> 12 #include <re_jbuf.h> 13 14 15 #define DEBUG_MODULE "jbuf" 16 #define DEBUG_LEVEL 5 17 #include <re_dbg.h> 18 19 20 #ifndef RELEASE 21 #define JBUF_STAT 1 /**< Jitter buffer statistics */ 22 #endif 23 24 25 #if JBUF_STAT 26 #define STAT_ADD(var, value) (jb->stat.var) += (value) /**< Stats add */ 27 #define STAT_INC(var) ++(jb->stat.var) /**< Stats inc */ 28 #else 29 #define STAT_ADD(var, value) 30 #define STAT_INC(var) 31 #endif 32 33 34 /** Defines a packet frame */ 35 struct frame { 36 struct le le; /**< Linked list element */ 37 struct rtp_header hdr; /**< RTP Header */ 38 void *mem; /**< Reference counted pointer */ 39 }; 40 41 42 /** 43 * Defines a jitter buffer 44 * 45 * The jitter buffer is for incoming RTP packets, which are sorted by 46 * sequence number. 47 */ 48 struct jbuf { 49 struct list pooll; /**< List of free frames in pool */ 50 struct list framel; /**< List of buffered frames */ 51 uint32_t n; /**< [# frames] Current # of frames in buffer */ 52 uint32_t min; /**< [# frames] Minimum # of frames to buffer */ 53 uint32_t max; /**< [# frames] Maximum # of frames to buffer */ 54 uint16_t seq_put; /**< Sequence number for last jbuf_put() */ 55 bool running; /**< Jitter buffer is running */ 56 57 #if JBUF_STAT 58 uint16_t seq_get; /**< Timestamp of last played frame */ 59 struct jbuf_stat stat; /**< Jitter buffer Statistics */ 60 #endif 61 }; 62 63 64 /** Is x less than y? */ 65 static inline bool seq_less(uint16_t x, uint16_t y) 66 { 67 return ((int16_t)(x - y)) < 0; 68 } 69 70 71 /** 72 * Get a frame from the pool 73 */ 74 static void frame_alloc(struct jbuf *jb, struct frame **f) 75 { 76 struct le *le; 77 78 le = jb->pooll.head; 79 if (le) { 80 list_unlink(le); 81 ++jb->n; 82 } 83 else { 84 struct frame *f0; 85 86 /* Steal an old frame */ 87 le = jb->framel.head; 88 f0 = le->data; 89 90 STAT_INC(n_overflow); 91 DEBUG_INFO("drop 1 old frame seq=%u (total dropped %u)\n", 92 f0->hdr.seq, jb->stat.n_overflow); 93 94 f0->mem = mem_deref(f0->mem); 95 list_unlink(le); 96 } 97 98 *f = le->data; 99 } 100 101 102 /** 103 * Release a frame, put it back in the pool 104 */ 105 static void frame_deref(struct jbuf *jb, struct frame *f) 106 { 107 f->mem = mem_deref(f->mem); 108 list_unlink(&f->le); 109 list_append(&jb->pooll, &f->le, f); 110 --jb->n; 111 } 112 113 114 static void jbuf_destructor(void *data) 115 { 116 struct jbuf *jb = data; 117 118 jbuf_flush(jb); 119 120 /* Free all frames in the pool list */ 121 list_flush(&jb->pooll); 122 } 123 124 125 /** 126 * Allocate a new jitter buffer 127 * 128 * @param jbp Pointer to returned jitter buffer 129 * @param min Minimum delay in [frames] 130 * @param max Maximum delay in [frames] 131 * 132 * @return 0 if success, otherwise errorcode 133 */ 134 int jbuf_alloc(struct jbuf **jbp, uint32_t min, uint32_t max) 135 { 136 struct jbuf *jb; 137 uint32_t i; 138 int err = 0; 139 140 if (!jbp || ( min > max)) 141 return EINVAL; 142 143 DEBUG_INFO("alloc: delay=%u-%u frames\n", min, max); 144 145 /* self-test: x < y (also handle wrap around) */ 146 if (!seq_less(10, 20) || seq_less(20, 10) || !seq_less(65535, 0)) { 147 DEBUG_WARNING("seq_less() is broken\n"); 148 return ENOSYS; 149 } 150 151 jb = mem_zalloc(sizeof(*jb), jbuf_destructor); 152 if (!jb) 153 return ENOMEM; 154 155 list_init(&jb->pooll); 156 list_init(&jb->framel); 157 158 jb->min = min; 159 jb->max = max; 160 161 /* Allocate all frames now */ 162 for (i=0; i<jb->max; i++) { 163 struct frame *f = mem_zalloc(sizeof(*f), NULL); 164 if (!f) { 165 err = ENOMEM; 166 break; 167 } 168 169 list_append(&jb->pooll, &f->le, f); 170 DEBUG_INFO("alloc: adding to pool list %u\n", i); 171 } 172 173 if (err) 174 mem_deref(jb); 175 else 176 *jbp = jb; 177 178 return err; 179 } 180 181 182 /** 183 * Put one frame into the jitter buffer 184 * 185 * @param jb Jitter buffer 186 * @param hdr RTP Header 187 * @param mem Memory pointer - will be referenced 188 * 189 * @return 0 if success, otherwise errorcode 190 */ 191 int jbuf_put(struct jbuf *jb, const struct rtp_header *hdr, void *mem) 192 { 193 struct frame *f; 194 struct le *le, *tail; 195 uint16_t seq; 196 int err = 0; 197 198 if (!jb || !hdr) 199 return EINVAL; 200 201 seq = hdr->seq; 202 203 STAT_INC(n_put); 204 205 if (jb->running) { 206 207 /* Packet arrived too late to be put into buffer */ 208 if (seq_less((seq + jb->n), jb->seq_put)) { 209 STAT_INC(n_late); 210 DEBUG_INFO("packet too late: seq=%u (seq_put=%u)\n", 211 seq, jb->seq_put); 212 return ETIMEDOUT; 213 } 214 } 215 216 frame_alloc(jb, &f); 217 218 tail = jb->framel.tail; 219 220 /* If buffer is empty -> append to tail 221 Frame is later than tail -> append to tail 222 */ 223 if (!tail || seq_less(((struct frame *)tail->data)->hdr.seq, seq)) { 224 list_append(&jb->framel, &f->le, f); 225 goto out; 226 } 227 228 /* Out-of-sequence, find right position */ 229 for (le = tail; le; le = le->prev) { 230 const uint16_t seq_le = ((struct frame *)le->data)->hdr.seq; 231 232 if (seq_less(seq_le, seq)) { /* most likely */ 233 DEBUG_INFO("put: out-of-sequence" 234 " - inserting after seq=%u (seq=%u)\n", 235 seq_le, seq); 236 list_insert_after(&jb->framel, le, &f->le, f); 237 break; 238 } 239 else if (seq == seq_le) { /* less likely */ 240 /* Detect duplicates */ 241 DEBUG_INFO("duplicate: seq=%u\n", seq); 242 STAT_INC(n_dups); 243 list_insert_after(&jb->framel, le, &f->le, f); 244 frame_deref(jb, f); 245 return EALREADY; 246 } 247 248 /* sequence number less than current seq, continue */ 249 } 250 251 /* no earlier timestamps found, put in head */ 252 if (!le) { 253 DEBUG_INFO("put: out-of-sequence" 254 " - put in head (seq=%u)\n", seq); 255 list_prepend(&jb->framel, &f->le, f); 256 } 257 258 STAT_INC(n_oos); 259 260 out: 261 /* Update last timestamp */ 262 jb->running = true; 263 jb->seq_put = seq; 264 265 /* Success */ 266 f->hdr = *hdr; 267 f->mem = mem_ref(mem); 268 269 return err; 270 } 271 272 273 /** 274 * Get one frame from the jitter buffer 275 * 276 * @param jb Jitter buffer 277 * @param hdr Returned RTP Header 278 * @param mem Pointer to memory object storage - referenced on success 279 * 280 * @return 0 if success, otherwise errorcode 281 */ 282 int jbuf_get(struct jbuf *jb, struct rtp_header *hdr, void **mem) 283 { 284 struct frame *f; 285 286 if (!jb || !hdr || !mem) 287 return EINVAL; 288 289 STAT_INC(n_get); 290 291 if (jb->n <= jb->min || !jb->framel.head) { 292 DEBUG_INFO("not enough buffer frames - wait.. (n=%u min=%u)\n", 293 jb->n, jb->min); 294 STAT_INC(n_underflow); 295 return ENOENT; 296 } 297 298 /* When we get one frame F[i], check that the next frame F[i+1] 299 is present and have a seq no. of seq[i] + 1 ! 300 if not, we should consider that packet lost */ 301 302 f = jb->framel.head->data; 303 304 #if JBUF_STAT 305 /* Check timestamp of previously played frame */ 306 if (jb->seq_get) { 307 const int16_t seq_diff = f->hdr.seq - jb->seq_get; 308 if (seq_less(f->hdr.seq, jb->seq_get)) { 309 DEBUG_WARNING("get: seq=%u too late\n", f->hdr.seq); 310 } 311 else if (seq_diff > 1) { 312 STAT_ADD(n_lost, 1); 313 DEBUG_INFO("get: n_lost: diff=%d,seq=%u,seq_get=%u\n", 314 seq_diff, f->hdr.seq, jb->seq_get); 315 } 316 } 317 318 /* Update sequence number for 'get' */ 319 jb->seq_get = f->hdr.seq; 320 #endif 321 322 *hdr = f->hdr; 323 *mem = mem_ref(f->mem); 324 325 frame_deref(jb, f); 326 327 return 0; 328 } 329 330 331 /** 332 * Flush all frames in the jitter buffer 333 * 334 * @param jb Jitter buffer 335 */ 336 void jbuf_flush(struct jbuf *jb) 337 { 338 struct le *le; 339 340 if (!jb) 341 return; 342 343 if (jb->framel.head) { 344 DEBUG_INFO("flush: %u frames\n", jb->n); 345 } 346 347 /* put all buffered frames back in free list */ 348 for (le = jb->framel.head; le; le = jb->framel.head) { 349 DEBUG_INFO(" flush frame: seq=%u\n", 350 ((struct frame *)(le->data))->hdr.seq); 351 352 frame_deref(jb, le->data); 353 } 354 355 jb->n = 0; 356 jb->running = false; 357 358 STAT_INC(n_flush); 359 } 360 361 362 /** 363 * Get jitter buffer statistics 364 * 365 * @param jb Jitter buffer 366 * @param jstat Pointer to statistics storage 367 * 368 * @return 0 if success, otherwise errorcode 369 */ 370 int jbuf_stats(const struct jbuf *jb, struct jbuf_stat *jstat) 371 { 372 if (!jb || !jstat) 373 return EINVAL; 374 375 #if JBUF_STAT 376 *jstat = jb->stat; 377 378 return 0; 379 #else 380 return ENOSYS; 381 #endif 382 } 383 384 385 /** 386 * Debug the jitter buffer 387 * 388 * @param pf Print handler 389 * @param jb Jitter buffer 390 * 391 * @return 0 if success, otherwise errorcode 392 */ 393 int jbuf_debug(struct re_printf *pf, const struct jbuf *jb) 394 { 395 int err = 0; 396 397 if (!jb) 398 return 0; 399 400 err |= re_hprintf(pf, "--- jitter buffer debug---\n"); 401 402 err |= re_hprintf(pf, " running=%d", jb->running); 403 err |= re_hprintf(pf, " min=%u cur=%u max=%u [frames]\n", 404 jb->min, jb->n, jb->max); 405 err |= re_hprintf(pf, " seq_put=%u\n", jb->seq_put); 406 407 #if JBUF_STAT 408 err |= re_hprintf(pf, " Stat: put=%u", jb->stat.n_put); 409 err |= re_hprintf(pf, " get=%u", jb->stat.n_get); 410 err |= re_hprintf(pf, " oos=%u", jb->stat.n_oos); 411 err |= re_hprintf(pf, " dup=%u", jb->stat.n_dups); 412 err |= re_hprintf(pf, " late=%u", jb->stat.n_late); 413 err |= re_hprintf(pf, " or=%u", jb->stat.n_overflow); 414 err |= re_hprintf(pf, " ur=%u", jb->stat.n_underflow); 415 err |= re_hprintf(pf, " flush=%u", jb->stat.n_flush); 416 err |= re_hprintf(pf, " put/get_ratio=%u%%", jb->stat.n_get ? 417 100*jb->stat.n_put/jb->stat.n_get : 0); 418 err |= re_hprintf(pf, " lost=%u (%u.%02u%%)\n", 419 jb->stat.n_lost, 420 jb->stat.n_put ? 421 100*jb->stat.n_lost/jb->stat.n_put : 0, 422 jb->stat.n_put ? 423 10000*jb->stat.n_lost/jb->stat.n_put%100 : 0); 424 #endif 425 426 return err; 427 } 428