Debian Codegraph @

srtcore/queue.h

raw
1 /*
2 * SRT - Secure, Reliable, Transport
3 * Copyright (c) 2018 Haivision Systems Inc.
4 *
5 * This Source Code Form is subject to the terms of the Mozilla Public
6 * License, v. 2.0. If a copy of the MPL was not distributed with this
7 * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 *
9 */
10
11 /*****************************************************************************
12 Copyright (c) 2001 - 2011, The Board of Trustees of the University of Illinois.
13 All rights reserved.
14
15 Redistribution and use in source and binary forms, with or without
16 modification, are permitted provided that the following conditions are
17 met:
18
19 * Redistributions of source code must retain the above
20 copyright notice, this list of conditions and the
21 following disclaimer.
22
23 * Redistributions in binary form must reproduce the
24 above copyright notice, this list of conditions
25 and the following disclaimer in the documentation
26 and/or other materials provided with the distribution.
27
28 * Neither the name of the University of Illinois
29 nor the names of its contributors may be used to
30 endorse or promote products derived from this
31 software without specific prior written permission.
32
33 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
34 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
35 THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
36 PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
37 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
38 EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
39 PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
40 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
41 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
42 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
43 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
44 *****************************************************************************/
45
46 /*****************************************************************************
47 written by
48 Yunhong Gu, last updated 01/12/2011
49 modified by
50 Haivision Systems Inc.
51 *****************************************************************************/
52
53 #ifndef INC_SRT_QUEUE_H
54 #define INC_SRT_QUEUE_H
55
56 #include "common.h"
57 #include "packet.h"
58 #include "socketconfig.h"
59 #include "netinet_any.h"
60 #include "utilities.h"
61 #include <list>
62 #include <map>
63 #include <queue>
64 #include <vector>
65
66 namespace srt
67 {
68 class CChannel;
69 class CUDT;
70
71 struct CUnit
72 {
73 CPacket m_Packet; // packet
74 sync::atomic<bool> m_bTaken; // true if the unit is is use (can be stored in the RCV buffer).
75 };
76
77 class CUnitQueue
78 {
79 public:
80 /// @brief Construct a unit queue.
81 /// @param mss Initial number of units to allocate.
82 /// @param mss Maximum segment size meaning the size of each unit.
83 /// @throws CUDTException SRT_ENOBUF.
84 CUnitQueue(int initNumUnits, int mss);
85 ~CUnitQueue();
86
87 public:
88 int capacity() const { return m_iSize; }
89 int size() const { return m_iSize - m_iNumTaken; }
90
91 public:
92 /// @brief Find an available unit for incoming packet. Allocate new units if 90% or more are in use.
93 /// @note This function is not thread-safe. Currently only CRcvQueue::worker thread calls it, thus
94 /// it is not an issue. However, must be protected if used from several threads in the future.
95 /// @return Pointer to the available unit, NULL if not found.
96 CUnit* getNextAvailUnit();
97
98 void makeUnitFree(CUnit* unit);
99
100 void makeUnitTaken(CUnit* unit);
101
102 private:
103 struct CQEntry
104 {
105 CUnit* m_pUnit; // unit queue
106 char* m_pBuffer; // data buffer
107 int m_iSize; // size of each queue
108
109 CQEntry* m_pNext;
110 };
111
112 /// Increase the unit queue size (by @a m_iBlockSize units).
113 /// Uses m_mtx to protect access and changes of the queue state.
114 /// @return 0: success, -1: failure.
115 int increase_();
116
117 /// @brief Allocated a CQEntry of iNumUnits with each unit of mss bytes.
118 /// @param iNumUnits a number of units to allocate
119 /// @param mss the size of each unit in bytes.
120 /// @return a pointer to a newly allocated entry on success, NULL otherwise.
121 static CQEntry* allocateEntry(const int iNumUnits, const int mss);
122
123 private:
124 CQEntry* m_pQEntry; // pointer to the first unit queue
125 CQEntry* m_pCurrQueue; // pointer to the current available queue
126 CQEntry* m_pLastQueue; // pointer to the last unit queue
127 CUnit* m_pAvailUnit; // recent available unit
128 int m_iSize; // total size of the unit queue, in number of packets
129 sync::atomic<int> m_iNumTaken; // total number of valid (occupied) packets in the queue
130 const int m_iMSS; // unit buffer size
131 const int m_iBlockSize; // Number of units in each CQEntry.
132
133 private:
134 CUnitQueue(const CUnitQueue&);
135 CUnitQueue& operator=(const CUnitQueue&);
136 };
137
138 struct CSNode
139 {
140 CUDT* m_pUDT; // Pointer to the instance of CUDT socket
141 sync::steady_clock::time_point m_tsTimeStamp;
142
143 sync::atomic<int> m_iHeapLoc; // location on the heap, -1 means not on the heap
144 };
145
146 class CSndUList
147 {
148 public:
149 CSndUList(sync::CTimer* pTimer);
150 ~CSndUList();
151
152 public:
153 enum EReschedule
154 {
155 DONT_RESCHEDULE = 0,
156 DO_RESCHEDULE = 1
157 };
158
159 static EReschedule rescheduleIf(bool cond) { return cond ? DO_RESCHEDULE : DONT_RESCHEDULE; }
160 void resetAtFork();
161
162 /// Update the timestamp of the UDT instance on the list.
163 /// @param [in] u pointer to the UDT instance
164 /// @param [in] reschedule if the timestamp should be rescheduled
165 /// @param [in] ts the next time to trigger sending logic on the CUDT
166 void update(const CUDT* u, EReschedule reschedule, sync::steady_clock::time_point ts = sync::steady_clock::now());
167
168 /// Retrieve the next (in time) socket from the heap to process its sending request.
169 /// @return a pointer to CUDT instance to process next.
170 CUDT* pop();
171
172 /// Remove UDT instance from the list.
173 /// @param [in] u pointer to the UDT instance
174 void remove(const CUDT* u);// EXCLUDES(m_ListLock);
175
176 /// Retrieve the next scheduled processing time.
177 /// @return Scheduled processing time of the first UDT socket in the list.
178 sync::steady_clock::time_point getNextProcTime();
179
180 /// Wait for the list to become non empty.
181 void waitNonEmpty() const;
182
183 /// Signal to stop waiting in waitNonEmpty().
184 void signalInterrupt() const;
185
186 private:
187 /// Doubles the size of the list.
188 ///
189 void realloc_();// REQUIRES(m_ListLock);
190
191 /// Insert a new UDT instance into the list with realloc if required.
192 ///
193 /// @param [in] ts time stamp: next processing time
194 /// @param [in] u pointer to the UDT instance
195 void insert_(const sync::steady_clock::time_point& ts, const CUDT* u);
196
197 /// Insert a new UDT instance into the list without realloc.
198 /// Should be called if there is a guaranteed space for the element.
199 ///
200 /// @param [in] ts time stamp: next processing time
201 /// @param [in] u pointer to the UDT instance
202 void insert_norealloc_(const sync::steady_clock::time_point& ts, const CUDT* u);// REQUIRES(m_ListLock);
203
204 /// Removes CUDT entry from the list.
205 /// If the last entry is removed, calls sync::CTimer::interrupt().
206 void remove_(const CUDT* u);
207
208 private:
209 CSNode** m_pHeap; // The heap array
210 int m_iArrayLength; // physical length of the array
211 int m_iLastEntry; // position of last entry on the heap array or -1 if empty.
212
213 mutable sync::Mutex m_ListLock; // Protects the list (m_pHeap, m_iArrayLength, m_iLastEntry).
214 mutable sync::Condition m_ListCond;
215
216 sync::CTimer* const m_pTimer;
217
218 private:
219 CSndUList(const CSndUList&);
220 CSndUList& operator=(const CSndUList&);
221 };
222
223 struct CRNode
224 {
225 CUDT* m_pUDT; // Pointer to the instance of CUDT socket
226 sync::steady_clock::time_point m_tsTimeStamp; // Time Stamp
227
228 CRNode* m_pPrev; // previous link
229 CRNode* m_pNext; // next link
230
231 sync::atomic<bool> m_bOnList; // if the node is already on the list
232 };
233
234 class CRcvUList
235 {
236 public:
237 CRcvUList();
238 ~CRcvUList();
239
240 public:
241 /// Insert a new UDT instance to the list.
242 /// @param [in] u pointer to the UDT instance
243
244 void insert(const CUDT* u);
245
246 /// Remove the UDT instance from the list.
247 /// @param [in] u pointer to the UDT instance
248
249 void remove(const CUDT* u);
250
251 /// Move the UDT instance to the end of the list, if it already exists; otherwise, do nothing.
252 /// @param [in] u pointer to the UDT instance
253
254 void update(const CUDT* u);
255
256 public:
257 CRNode* m_pUList; // the head node
258
259 private:
260 CRNode* m_pLast; // the last node
261
262 private:
263 CRcvUList(const CRcvUList&);
264 CRcvUList& operator=(const CRcvUList&);
265 };
266
267 class CHash
268 {
269 public:
270 CHash();
271 ~CHash();
272
273 public:
274 /// Initialize the hash table.
275 /// @param [in] size hash table size
276
277 void init(int size);
278
279 /// Look for a UDT instance from the hash table.
280 /// @param [in] id socket ID
281 /// @return Pointer to a UDT instance, or NULL if not found.
282
283 CUDT* lookup(int32_t id);
284
285 /// Insert an entry to the hash table.
286 /// @param [in] id socket ID
287 /// @param [in] u pointer to the UDT instance
288
289 void insert(int32_t id, CUDT* u);
290
291 /// Remove an entry from the hash table.
292 /// @param [in] id socket ID
293
294 void remove(int32_t id);
295
296 private:
297 struct CBucket
298 {
299 int32_t m_iID; // Socket ID
300 CUDT* m_pUDT; // Socket instance
301
302 CBucket* m_pNext; // next bucket
303 } * *m_pBucket; // list of buckets (the hash table)
304
305 int m_iHashSize; // size of hash table
306
307 private:
308 CHash(const CHash&);
309 CHash& operator=(const CHash&);
310 };
311
312 /// @brief A queue of sockets pending for connection.
313 /// It can be either a caller socket in a non-blocking mode
314 /// (the connection has to be handled in background),
315 /// or a socket in rendezvous connection mode.
316 class CRendezvousQueue
317 {
318 public:
319 CRendezvousQueue();
320 ~CRendezvousQueue();
321
322 public:
323 /// @brief Insert a new socket pending for connection (non-blocking caller or rendezvous).
324 /// @param id socket ID.
325 /// @param u pointer to a corresponding CUDT instance.
326 /// @param addr remote address to connect to.
327 /// @param ttl timepoint for connection attempt to expire.
328 void insert(const SRTSOCKET& id, CUDT* u, const sockaddr_any& addr, const srt::sync::steady_clock::time_point& ttl);
329
330 /// @brief Remove a socket from the connection pending list.
331 /// @param id socket ID.
332 void remove(const SRTSOCKET& id);
333
334 /// @brief Locate a socket in the connection pending queue.
335 /// @param addr source address of the packet received over UDP (peer address).
336 /// @param id socket ID.
337 /// @return a pointer to CUDT instance retrieved, or NULL if nothing was found.
338 CUDT* retrieve(const sockaddr_any& addr, SRTSOCKET& id) const;
339
340 /// @brief Update status of connections in the pending queue.
341 /// Stop connecting if TTL expires. Resend handshake request every 250 ms if no response from the peer.
342 /// @param rst result of reading from a UDP socket: received packet / nothing read / read error.
343 /// @param cst target status for pending connection: reject or proceed.
344 /// @param pktIn packet received from the UDP socket.
345 void updateConnStatus(EReadStatus rst, EConnectStatus cst, CUnit* unit);
346
347 private:
348 struct LinkStatusInfo
349 {
350 CUDT* u;
351 SRTSOCKET id;
352 int errorcode;
353 sockaddr_any peeraddr;
354 int token;
355
356 struct HasID
357 {
358 SRTSOCKET id;
359 HasID(SRTSOCKET p)
360 : id(p)
361 {
362 }
363 bool operator()(const LinkStatusInfo& i) { return i.id == id; }
364 };
365 };
366
367 /// @brief Qualify pending connections:
368 /// - Sockets with expired TTL go to the 'to_remove' list and removed from the queue straight away.
369 /// - If HS request is to be resent (resend 250 ms if no response from the peer) go to the 'to_process' list.
370 ///
371 /// @param rst result of reading from a UDP socket: received packet / nothing read / read error.
372 /// @param cst target status for pending connection: reject or proceed.
373 /// @param iDstSockID destination socket ID of the received packet.
374 /// @param[in,out] toRemove stores sockets with expired TTL.
375 /// @param[in,out] toProcess stores sockets which should repeat (resend) HS connection request.
376 bool qualifyToHandle(EReadStatus rst,
377 EConnectStatus cst,
378 int iDstSockID,
379 std::vector<LinkStatusInfo>& toRemove,
380 std::vector<LinkStatusInfo>& toProcess);
381
382 private:
383 struct CRL
384 {
385 SRTSOCKET m_iID; // SRT socket ID (self)
386 CUDT* m_pUDT; // CUDT instance
387 sockaddr_any m_PeerAddr; // SRT sonnection peer address
388 sync::steady_clock::time_point m_tsTTL; // the time that this request expires
389 };
390 std::list<CRL> m_lRendezvousID; // The sockets currently in rendezvous mode
391
392 mutable sync::Mutex m_RIDListLock;
393 };
394
395 class CSndQueue
396 {
397 friend class CUDT;
398 friend class CUDTUnited;
399
400 public:
401 CSndQueue();
402 ~CSndQueue();
403
404 public:
405 void resetAtFork();
406 // XXX There's currently no way to access the socket ID set for
407 // whatever the queue is currently working for. Required to find
408 // some way to do this, possibly by having a "reverse pointer".
409 // Currently just "unimplemented".
410 std::string CONID() const { return ""; }
411
412 /// Initialize the sending queue.
413 /// @param [in] c UDP channel to be associated to the queue
414 /// @param [in] t Timer
415 void init(CChannel* c, sync::CTimer* t);
416
417 /// Send out a packet to a given address. The @a src parameter is
418 /// blindly passed by the caller down the call with intention to
419 /// be received eventually by CChannel::sendto, and used only if
420 /// appropriate conditions state so.
421 /// @param [in] addr destination address
422 /// @param [in,ref] packet packet to be sent out
423 /// @param [in] src The source IP address (details above)
424 /// @return Size of data sent out.
425 int sendto(const sockaddr_any& addr, CPacket& packet, const sockaddr_any& src);
426
427 /// Get the IP TTL.
428 /// @param [in] ttl IP Time To Live.
429 /// @return TTL.
430 int getIpTTL() const;
431
432 /// Get the IP Type of Service.
433 /// @return ToS.
434 int getIpToS() const;
435
436 #ifdef SRT_ENABLE_BINDTODEVICE
437 bool getBind(char* dst, size_t len) const;
438 #endif
439
440 int ioctlQuery(int type) const;
441 int sockoptQuery(int level, int type) const;
442
443 void setClosing() { m_bClosing = true; }
444 void stop();
445
446 private:
447 static void* worker(void* param);
448 sync::CThread m_WorkerThread;
449
450 private:
451 CSndUList* m_pSndUList; // List of UDT instances for data sending
452 CChannel* m_pChannel; // The UDP channel for data sending
453 sync::CTimer* m_pTimer; // Timing facility
454
455 sync::atomic<bool> m_bClosing; // closing the worker
456
457 public:
458 #if defined(SRT_DEBUG_SNDQ_HIGHRATE) //>>debug high freq worker
459 sync::steady_clock::duration m_DbgPeriod;
460 mutable sync::steady_clock::time_point m_DbgTime;
461 struct
462 {
463 unsigned long lIteration; //
464 unsigned long lSleepTo; // SleepTo
465 unsigned long lNotReadyPop; // Continue
466 unsigned long lSendTo;
467 unsigned long lNotReadyTs;
468 unsigned long lCondWait; // block on m_WindowCond
469 } mutable m_WorkerStats;
470 #endif /* SRT_DEBUG_SNDQ_HIGHRATE */
471
472 private:
473
474 #if ENABLE_LOGGING
475 static srt::sync::atomic<int> m_counter;
476 #endif
477
478 CSndQueue(const CSndQueue&);
479 CSndQueue& operator=(const CSndQueue&);
480 };
481
482 class CRcvQueue
483 {
484 friend class CUDT;
485 friend class CUDTUnited;
486
487 public:
488 CRcvQueue();
489 ~CRcvQueue();
490
491 public:
492 void resetAtFork();
493 // XXX There's currently no way to access the socket ID set for
494 // whatever the queue is currently working. Required to find
495 // some way to do this, possibly by having a "reverse pointer".
496 // Currently just "unimplemented".
497 std::string CONID() const { return ""; }
498
499 /// Initialize the receiving queue.
500 /// @param [in] size queue size
501 /// @param [in] mss maximum packet size
502 /// @param [in] version IP version
503 /// @param [in] hsize hash table size
504 /// @param [in] c UDP channel to be associated to the queue
505 /// @param [in] t timer
506 void init(int size, size_t payload, int version, int hsize, CChannel* c, sync::CTimer* t);
507
508 /// Read a packet for a specific UDT socket id.
509 /// @param [in] id Socket ID
510 /// @param [out] packet received packet
511 /// @return Data size of the packet
512 int recvfrom(int32_t id, CPacket& to_packet);
513
514 void stopWorker();
515
516 void setClosing() { m_bClosing = true; }
517
518 int getIPversion() { return m_iIPversion; }
519
520 void stop();
521 private:
522 static void* worker(void* param);
523 sync::CThread m_WorkerThread;
524 // Subroutines of worker
525 EReadStatus worker_RetrieveUnit(int32_t& id, CUnit*& unit, sockaddr_any& sa);
526 EConnectStatus worker_ProcessConnectionRequest(CUnit* unit, const sockaddr_any& sa);
527 EConnectStatus worker_TryAsyncRend_OrStore(int32_t id, CUnit* unit, const sockaddr_any& sa);
528 EConnectStatus worker_ProcessAddressedPacket(int32_t id, CUnit* unit, const sockaddr_any& sa);
529
530 private:
531 CUnitQueue* m_pUnitQueue; // The received packet queue
532 CRcvUList* m_pRcvUList; // List of UDT instances that will read packets from the queue
533 CHash* m_pHash; // Hash table for UDT socket looking up
534 CChannel* m_pChannel; // UDP channel for receiving packets
535 sync::CTimer* m_pTimer; // shared timer with the snd queue
536
537 int m_iIPversion; // IP version
538 size_t m_szPayloadSize; // packet payload size
539
540 sync::atomic<bool> m_bClosing; // closing the worker
541 #if ENABLE_LOGGING
542 static srt::sync::atomic<int> m_counter; // A static counter to log RcvQueue worker thread number.
543 #endif
544
545 private:
546 bool setListener(CUDT* u);
547 CUDT* getListener();
548 bool removeListener(CUDT* u);
549
550 void registerConnector(const SRTSOCKET& id,
551 CUDT* u,
552 const sockaddr_any& addr,
553 const sync::steady_clock::time_point& ttl);
554 void removeConnector(const SRTSOCKET& id);
555
556 void setNewEntry(CUDT* u);
557 bool ifNewEntry();
558 CUDT* getNewEntry();
559
560 void storePktClone(int32_t id, const CPacket& pkt);
561
562 private:
563 sync::CSharedObjectPtr<CUDT> m_pListener; // pointer to the (unique, if any) listening UDT entity
564 CRendezvousQueue* m_pRendezvousQueue; // The list of sockets in rendezvous mode
565
566 std::vector<CUDT*> m_vNewEntry; // newly added entries, to be inserted
567 sync::Mutex m_IDLock;
568
569 std::map<int32_t, std::queue<CPacket*> > m_mBuffer; // temporary buffer for rendezvous connection request
570 sync::Mutex m_BufferLock;
571 sync::Condition m_BufferCond;
572
573 private:
574 CRcvQueue(const CRcvQueue&);
575 CRcvQueue& operator=(const CRcvQueue&);
576 };
577
578 struct CMultiplexer
579 {
580 CSndQueue* m_pSndQueue; // The sending queue
581 CRcvQueue* m_pRcvQueue; // The receiving queue
582 CChannel* m_pChannel; // The UDP channel for sending and receiving
583 sync::CTimer* m_pTimer; // The timer
584
585 int m_iPort; // The UDP port number of this multiplexer
586 int m_iIPversion; // Address family (AF_INET or AF_INET6)
587 int m_iRefCount; // number of UDT instances that are associated with this multiplexer
588
589 CSrtMuxerConfig m_mcfg;
590
591 int m_iID; // multiplexer ID
592
593 // Constructor should reset all pointers to NULL
594 // to prevent dangling pointer when checking for memory alloc fails
595 CMultiplexer()
596 : m_pSndQueue(NULL)
597 , m_pRcvQueue(NULL)
598 , m_pChannel(NULL)
599 , m_pTimer(NULL)
600 , m_iPort(0)
601 , m_iIPversion(0)
602 , m_iRefCount(1)
603 , m_iID(-1)
604 {
605 }
606
607 ~CMultiplexer()
608 {
609 if (m_pRcvQueue != NULL)
610 delete m_pRcvQueue;
611 if (m_pSndQueue != NULL)
612 delete m_pSndQueue;
613 if (m_pTimer != NULL)
614 delete m_pTimer;
615 close();
616 }
617 void resetAtFork();
618 void close();
619 void stop();
620 void destroy();
621 };
622
623 } // namespace srt
624
625 #endif