18.3.3.3 uORBDeviceMaster::getDeviceNode() 내부의 연결 리스트(Linked-list) 순회 및 검색 알고리즘
수십, 수백 개의 uORB 토픽 인스턴스들이 각자의 /obj 경로를 가지고 동적으로 생성되고 나면, 누군가는 이들을 효율적으로 관리하고 검색할 수 있는 중앙 장부가 필요하다. PX4에서 이 역할을 수행하는 전역 객체가 바로 싱글톤(Singleton)으로 동작하는 uORBDeviceMaster이다.
이 객체 내부에 존재하는 가장 핵심적인 메서드인 getDeviceNode()는 구독자나 발행자가 orb_subscribe 또는 orb_advertise를 호출할 때마다, 요구하는 토픽 이름과 인스턴스 ID에 정확히 일치하는 디바이스 노드의 메모리 주소를 찾아 반환하는 고도의 검색 알고리즘을 수행한다.
1. 디바이스 노드 관리 구조: 단일 연결 리스트(Singly Linked-list)
수많은 디바이스 노드(uORBDeviceNode 객체)들은 메모리 연속성을 보장할 수 없는 힙(Heap) 공간에 산발적으로 생성된다. uORBDeviceMaster는 메모리 단편화를 피하고 동적 크기 조절의 유연성을 극대화하기 위해 배열(Array) 방식 대신 단일 연결 리스트(Singly Linked-list) 구조를 채택했다.
uORBDeviceMaster 클래스 내부에는 단순히 리스트의 시작점을 가리키는 _node_list 포인터 변수 하나만이 존재하며, 각 uORBDeviceNode 객체들은 자신 내부에 다음 노드의 주소를 담고 있는 _sibling 포인터를 품고 있어 줄줄이 엮여 있는 형태를 띤다.
2. 순회(Traversal) 및 검색 알고리즘의 동작 과정
특정 모듈이 “센서 가속도계 1번 인스턴스(sensor_accel, 1)“를 찾기 위해 getDeviceNode()를 호출하면, 내부적으로 다음과 같은 매칭(Matching) 작업이 일어난다.
- 뮤텍스 락(Mutex Lock) 획득: 다중 스레드 환경에서 발생할 수 있는 데이터 경합(Race Condition)을 방지하기 위해, 리스트를 순회하기 전 반드시 스핀락(Spinlock) 또는 뮤텍스(Mutex)를 걸어 리스트 접근을 단독으로 점유한다.
- 헤드(Head)부터 선형 탐색(Linear Search):
_node_list포인터가 가리키는 첫 번째 노드부터 순차적으로 방문(node = node->_sibling)을 시작한다. - 메타데이터(Metadata) 비교: 방문한 노드의
o_name속성(문자열 포인터 비교)을 검사하여 동일한 토픽인지 확인한다. - 인스턴스 ID(Instance ID) 검증: 토픽 이름이 같다면, 그다음으로 해당 노드의 내부 상태 변수인
_instance값과 매개변수로 넘어온 인스턴스 번호가 일치하는지 2차 비교를 수행한다. - Hit 또는 Miss 반환: 두 조건이 모두 일치하는 노드를 발견하면 탐색을 즉시 종료하고 해당 객체의 포인터를 반환한다. 만약 리스트의 끝(
_sibling == nullptr)에 도달할 때까지 찾지 못했다면nullptr를 반환하여 아직 존재하지 않는 토픽임을 알린다.
3. 시간 복잡도(O(n))와 최적화 철학
단순 연결 리스트 기반의 선형 탐색 방식을 사용하므로 getDeviceNode()의 시간 복잡도(Time Complexity)는 엄밀히 말해 O(N) 이다. 해시 맵(Hash Map)이나 이진 탐색 트리(BST)와 같은 고급 자료구조를 쓸 경우 O(1)이나 O(\log N) 의 성능을 낼 수도 있을 텐데, 왜 굳이 느린 연결 리스트를 고집했을까?
그 이유는 **호출 빈도와 메모리 사용량의 트레이드오프(Trade-off)**를 절묘하게 계산한 PX4 아키텍트들의 통찰이다. getDeviceNode()를 통한 노드 검색은 시스템 부팅 시점인 초기화(Initialization) 단계에서만 집중적으로 발생한다. 일단 노드 주소를 찾아내어 구독자 객체에 할당(orb_subscribe())하거나 파일 디스크립터(FD)를 활성화해 놓은 뒤의 실시간 비행 루프에서는, 폴링(poll)과 read/write 작업이 메모리 포인터 접근으로 직접 이루어지므로 이 함수가 다시 호출될 일은 거의 없다.
따라서 런타임 성능에 전혀 영향을 주지 않는 부분을 무겁고 복잡한 해시 맵으로 설계하여 귀중한 RAM을 낭비하기보다는, 가장 단순하고 가벼우며 코어 메모리를 아낄 수 있는 연결 리스트를 채택한 것이다.