diff --git a/libs/binder/RpcState.cpp b/libs/binder/RpcState.cpp
index f181a7b..59643ba 100644
--- a/libs/binder/RpcState.cpp
+++ b/libs/binder/RpcState.cpp
@@ -52,7 +52,7 @@
 RpcState::~RpcState() {}
 
 status_t RpcState::onBinderLeaving(const sp<RpcSession>& session, const sp<IBinder>& binder,
-                                   RpcAddress* outAddress) {
+                                   uint64_t* outAddress) {
     bool isRemote = binder->remoteBinder();
     bool isRpc = isRemote && binder->remoteBinder()->isRpcBinder();
 
@@ -84,12 +84,11 @@
     for (auto& [addr, node] : mNodeForAddress) {
         if (binder == node.binder) {
             if (isRpc) {
-                const RpcAddress& actualAddr =
+                // check integrity of data structure
+                uint64_t actualAddr =
                         binder->remoteBinder()->getPrivateAccessorForId().rpcAddress();
-                // TODO(b/182939933): this is only checking integrity of data structure
-                // a different data structure doesn't need this
-                LOG_ALWAYS_FATAL_IF(addr < actualAddr, "Address mismatch");
-                LOG_ALWAYS_FATAL_IF(actualAddr < addr, "Address mismatch");
+                LOG_ALWAYS_FATAL_IF(addr != actualAddr, "Address mismatch %" PRIu64 " vs %" PRIu64,
+                                    addr, actualAddr);
             }
             node.timesSent++;
             node.sentRef = binder; // might already be set
@@ -101,8 +100,29 @@
 
     bool forServer = session->server() != nullptr;
 
-    for (size_t tries = 0; tries < 5; tries++) {
-        auto&& [it, inserted] = mNodeForAddress.insert({RpcAddress::random(forServer),
+    // arbitrary limit for maximum number of nodes in a process (otherwise we
+    // might run out of addresses)
+    if (mNodeForAddress.size() > 100000) {
+        return NO_MEMORY;
+    }
+
+    while (true) {
+        RpcWireAddress address{
+                .options = RPC_WIRE_ADDRESS_OPTION_CREATED,
+                .address = mNextId,
+        };
+        if (forServer) {
+            address.options |= RPC_WIRE_ADDRESS_OPTION_FOR_SERVER;
+        }
+
+        // avoid ubsan abort
+        if (mNextId >= std::numeric_limits<uint32_t>::max()) {
+            mNextId = 0;
+        } else {
+            mNextId++;
+        }
+
+        auto&& [it, inserted] = mNodeForAddress.insert({RpcWireAddress::toRaw(address),
                                                         BinderNode{
                                                                 .binder = binder,
                                                                 .timesSent = 1,
@@ -112,18 +132,10 @@
             *outAddress = it->first;
             return OK;
         }
-
-        // well, we don't have visibility into the header here, but still
-        static_assert(sizeof(RpcWireAddress) == 40, "this log needs updating");
-        ALOGW("2**256 is 1e77. If you see this log, you probably have some entropy issue, or maybe "
-              "you witness something incredible!");
     }
-
-    ALOGE("Unable to create an address in order to send out %p", binder.get());
-    return WOULD_BLOCK;
 }
 
-status_t RpcState::onBinderEntering(const sp<RpcSession>& session, const RpcAddress& address,
+status_t RpcState::onBinderEntering(const sp<RpcSession>& session, uint64_t address,
                                     sp<IBinder>* out) {
     // ensure that: if we want to use addresses for something else in the future (for
     //   instance, allowing transitive binder sends), that we don't accidentally
@@ -133,8 +145,11 @@
     //   if we communicate with a binder, it could always be proxying
     //   information. However, we want to make sure that isn't done on accident
     //   by a client.
-    if (!address.isRecognizedType()) {
-        ALOGE("Address is of an unknown type, rejecting: %s", address.toString().c_str());
+    RpcWireAddress addr = RpcWireAddress::fromRaw(address);
+    constexpr uint32_t kKnownOptions =
+            RPC_WIRE_ADDRESS_OPTION_CREATED | RPC_WIRE_ADDRESS_OPTION_FOR_SERVER;
+    if (addr.options & ~kKnownOptions) {
+        ALOGE("Address is of an unknown type, rejecting: %" PRIu64, address);
         return BAD_VALUE;
     }
 
@@ -159,9 +174,9 @@
 
     // we don't know about this binder, so the other side of the connection
     // should have created it.
-    if (address.isForServer() == !!session->server()) {
-        ALOGE("Server received unrecognized address which we should own the creation of %s.",
-              address.toString().c_str());
+    if ((addr.options & RPC_WIRE_ADDRESS_OPTION_FOR_SERVER) == !!session->server()) {
+        ALOGE("Server received unrecognized address which we should own the creation of %" PRIu64,
+              address);
         return BAD_VALUE;
     }
 
@@ -241,9 +256,8 @@
             desc = "(null)";
         }
 
-        ALOGE("- BINDER NODE: %p times sent:%zu times recd: %zu a:%s type:%s",
-              node.binder.unsafe_get(), node.timesSent, node.timesRecd, address.toString().c_str(),
-              desc);
+        ALOGE("- BINDER NODE: %p times sent:%zu times recd: %zu a: %" PRIu64 " type: %s",
+              node.binder.unsafe_get(), node.timesSent, node.timesRecd, address, desc);
     }
     ALOGE("END DUMP OF RpcState");
 }
@@ -360,8 +374,8 @@
     data.markForRpc(session);
     Parcel reply;
 
-    status_t status = transactAddress(connection, RpcAddress::zero(), RPC_SPECIAL_TRANSACT_GET_ROOT,
-                                      data, session, &reply, 0);
+    status_t status =
+            transactAddress(connection, 0, RPC_SPECIAL_TRANSACT_GET_ROOT, data, session, &reply, 0);
     if (status != OK) {
         ALOGE("Error getting root object: %s", statusToString(status).c_str());
         return nullptr;
@@ -376,9 +390,8 @@
     data.markForRpc(session);
     Parcel reply;
 
-    status_t status =
-            transactAddress(connection, RpcAddress::zero(), RPC_SPECIAL_TRANSACT_GET_MAX_THREADS,
-                            data, session, &reply, 0);
+    status_t status = transactAddress(connection, 0, RPC_SPECIAL_TRANSACT_GET_MAX_THREADS, data,
+                                      session, &reply, 0);
     if (status != OK) {
         ALOGE("Error getting max threads: %s", statusToString(status).c_str());
         return status;
@@ -402,9 +415,8 @@
     data.markForRpc(session);
     Parcel reply;
 
-    status_t status =
-            transactAddress(connection, RpcAddress::zero(), RPC_SPECIAL_TRANSACT_GET_SESSION_ID,
-                            data, session, &reply, 0);
+    status_t status = transactAddress(connection, 0, RPC_SPECIAL_TRANSACT_GET_SESSION_ID, data,
+                                      session, &reply, 0);
     if (status != OK) {
         ALOGE("Error getting session ID: %s", statusToString(status).c_str());
         return status;
@@ -426,26 +438,26 @@
         return BAD_TYPE;
     }
 
-    RpcAddress address = RpcAddress::zero();
+    uint64_t address;
     if (status_t status = onBinderLeaving(session, binder, &address); status != OK) return status;
 
     return transactAddress(connection, address, code, data, session, reply, flags);
 }
 
 status_t RpcState::transactAddress(const sp<RpcSession::RpcConnection>& connection,
-                                   const RpcAddress& address, uint32_t code, const Parcel& data,
+                                   uint64_t address, uint32_t code, const Parcel& data,
                                    const sp<RpcSession>& session, Parcel* reply, uint32_t flags) {
     LOG_ALWAYS_FATAL_IF(!data.isForRpc());
     LOG_ALWAYS_FATAL_IF(data.objectsCount() != 0);
 
     uint64_t asyncNumber = 0;
 
-    if (!address.isZero()) {
+    if (address != 0) {
         std::unique_lock<std::mutex> _l(mNodeMutex);
         if (mTerminated) return DEAD_OBJECT; // avoid fatal only, otherwise races
         auto it = mNodeForAddress.find(address);
-        LOG_ALWAYS_FATAL_IF(it == mNodeForAddress.end(), "Sending transact on unknown address %s",
-                            address.toString().c_str());
+        LOG_ALWAYS_FATAL_IF(it == mNodeForAddress.end(),
+                            "Sending transact on unknown address %" PRIu64, address);
 
         if (flags & IBinder::FLAG_ONEWAY) {
             asyncNumber = it->second.asyncNumber;
@@ -466,8 +478,9 @@
             .command = RPC_COMMAND_TRANSACT,
             .bodySize = static_cast<uint32_t>(sizeof(RpcWireTransaction) + data.dataSize()),
     };
+
     RpcWireTransaction transaction{
-            .address = address.viewRawEmbedded(),
+            .address = RpcWireAddress::fromRaw(address),
             .code = code,
             .flags = flags,
             .asyncNumber = asyncNumber,
@@ -557,15 +570,14 @@
 }
 
 status_t RpcState::sendDecStrong(const sp<RpcSession::RpcConnection>& connection,
-                                 const sp<RpcSession>& session, const RpcAddress& addr) {
+                                 const sp<RpcSession>& session, uint64_t addr) {
     {
         std::lock_guard<std::mutex> _l(mNodeMutex);
         if (mTerminated) return DEAD_OBJECT; // avoid fatal only, otherwise races
         auto it = mNodeForAddress.find(addr);
-        LOG_ALWAYS_FATAL_IF(it == mNodeForAddress.end(), "Sending dec strong on unknown address %s",
-                            addr.toString().c_str());
-        LOG_ALWAYS_FATAL_IF(it->second.timesRecd <= 0, "Bad dec strong %s",
-                            addr.toString().c_str());
+        LOG_ALWAYS_FATAL_IF(it == mNodeForAddress.end(),
+                            "Sending dec strong on unknown address %" PRIu64, addr);
+        LOG_ALWAYS_FATAL_IF(it->second.timesRecd <= 0, "Bad dec strong %" PRIu64, addr);
 
         it->second.timesRecd--;
         LOG_ALWAYS_FATAL_IF(nullptr != tryEraseNode(it),
@@ -579,8 +591,7 @@
     if (status_t status = rpcSend(connection, session, "dec ref header", &cmd, sizeof(cmd));
         status != OK)
         return status;
-    if (status_t status = rpcSend(connection, session, "dec ref body", &addr.viewRawEmbedded(),
-                                  sizeof(RpcWireAddress));
+    if (status_t status = rpcSend(connection, session, "dec ref body", &addr, sizeof(addr));
         status != OK)
         return status;
     return OK;
@@ -685,14 +696,12 @@
     }
     RpcWireTransaction* transaction = reinterpret_cast<RpcWireTransaction*>(transactionData.data());
 
-    // TODO(b/182939933): heap allocation just for lookup in mNodeForAddress,
-    // maybe add an RpcAddress 'view' if the type remains 'heavy'
-    auto addr = RpcAddress::fromRawEmbedded(&transaction->address);
+    uint64_t addr = RpcWireAddress::toRaw(transaction->address);
     bool oneway = transaction->flags & IBinder::FLAG_ONEWAY;
 
     status_t replyStatus = OK;
     sp<IBinder> target;
-    if (!addr.isZero()) {
+    if (addr != 0) {
         if (!targetRef) {
             replyStatus = onBinderEntering(session, addr, &target);
         } else {
@@ -708,21 +717,21 @@
             // (any binder which is being transacted on should be holding a
             // strong ref count), so in either case, terminating the
             // session.
-            ALOGE("While transacting, binder has been deleted at address %s. Terminating!",
-                  addr.toString().c_str());
+            ALOGE("While transacting, binder has been deleted at address %" PRIu64 ". Terminating!",
+                  addr);
             (void)session->shutdownAndWait(false);
             replyStatus = BAD_VALUE;
         } else if (target->localBinder() == nullptr) {
-            ALOGE("Unknown binder address or non-local binder, not address %s. Terminating!",
-                  addr.toString().c_str());
+            ALOGE("Unknown binder address or non-local binder, not address %" PRIu64
+                  ". Terminating!",
+                  addr);
             (void)session->shutdownAndWait(false);
             replyStatus = BAD_VALUE;
         } else if (oneway) {
             std::unique_lock<std::mutex> _l(mNodeMutex);
             auto it = mNodeForAddress.find(addr);
             if (it->second.binder.promote() != target) {
-                ALOGE("Binder became invalid during transaction. Bad client? %s",
-                      addr.toString().c_str());
+                ALOGE("Binder became invalid during transaction. Bad client? %" PRIu64, addr);
                 replyStatus = BAD_VALUE;
             } else if (transaction->asyncNumber != it->second.asyncNumber) {
                 // we need to process some other asynchronous transaction
@@ -734,8 +743,8 @@
                 });
 
                 size_t numPending = it->second.asyncTodo.size();
-                LOG_RPC_DETAIL("Enqueuing %" PRId64 " on %s (%zu pending)",
-                               transaction->asyncNumber, addr.toString().c_str(), numPending);
+                LOG_RPC_DETAIL("Enqueuing %" PRIu64 " on %" PRIu64 " (%zu pending)",
+                               transaction->asyncNumber, addr, numPending);
 
                 constexpr size_t kArbitraryOnewayCallTerminateLevel = 10000;
                 constexpr size_t kArbitraryOnewayCallWarnLevel = 1000;
@@ -820,8 +829,8 @@
             ALOGW("Oneway call failed with error: %d", replyStatus);
         }
 
-        LOG_RPC_DETAIL("Processed async transaction %" PRId64 " on %s", transaction->asyncNumber,
-                       addr.toString().c_str());
+        LOG_RPC_DETAIL("Processed async transaction %" PRIu64 " on %" PRIu64,
+                       transaction->asyncNumber, addr);
 
         // Check to see if there is another asynchronous transaction to process.
         // This behavior differs from binder behavior, since in the binder
@@ -847,8 +856,8 @@
 
             if (it->second.asyncTodo.size() == 0) return OK;
             if (it->second.asyncTodo.top().asyncNumber == it->second.asyncNumber) {
-                LOG_RPC_DETAIL("Found next async transaction %" PRId64 " on %s",
-                               it->second.asyncNumber, addr.toString().c_str());
+                LOG_RPC_DETAIL("Found next async transaction %" PRIu64 " on %" PRIu64,
+                               it->second.asyncNumber, addr);
 
                 // justification for const_cast (consider avoiding priority_queue):
                 // - AsyncTodo operator< doesn't depend on 'data' or 'ref' objects
@@ -904,7 +913,7 @@
         status != OK)
         return status;
 
-    if (command.bodySize < sizeof(RpcWireAddress)) {
+    if (command.bodySize != sizeof(RpcWireAddress)) {
         ALOGE("Expecting %zu but got %" PRId32 " bytes for RpcWireAddress. Terminating!",
               sizeof(RpcWireAddress), command.bodySize);
         (void)session->shutdownAndWait(false);
@@ -912,31 +921,32 @@
     }
     RpcWireAddress* address = reinterpret_cast<RpcWireAddress*>(commandData.data());
 
-    // TODO(b/182939933): heap allocation just for lookup
-    auto addr = RpcAddress::fromRawEmbedded(address);
+    uint64_t addr = RpcWireAddress::toRaw(*address);
+
     std::unique_lock<std::mutex> _l(mNodeMutex);
     auto it = mNodeForAddress.find(addr);
     if (it == mNodeForAddress.end()) {
-        ALOGE("Unknown binder address %s for dec strong.", addr.toString().c_str());
+        ALOGE("Unknown binder address %" PRIu64 " for dec strong.", addr);
         return OK;
     }
 
     sp<IBinder> target = it->second.binder.promote();
     if (target == nullptr) {
-        ALOGE("While requesting dec strong, binder has been deleted at address %s. Terminating!",
-              addr.toString().c_str());
+        ALOGE("While requesting dec strong, binder has been deleted at address %" PRIu64
+              ". Terminating!",
+              addr);
         _l.unlock();
         (void)session->shutdownAndWait(false);
         return BAD_VALUE;
     }
 
     if (it->second.timesSent == 0) {
-        ALOGE("No record of sending binder, but requested decStrong: %s", addr.toString().c_str());
+        ALOGE("No record of sending binder, but requested decStrong: %" PRIu64, addr);
         return OK;
     }
 
-    LOG_ALWAYS_FATAL_IF(it->second.sentRef == nullptr, "Inconsistent state, lost ref for %s",
-                        addr.toString().c_str());
+    LOG_ALWAYS_FATAL_IF(it->second.sentRef == nullptr, "Inconsistent state, lost ref for %" PRIu64,
+                        addr);
 
     it->second.timesSent--;
     sp<IBinder> tempHold = tryEraseNode(it);
@@ -946,7 +956,7 @@
     return OK;
 }
 
-sp<IBinder> RpcState::tryEraseNode(std::map<RpcAddress, BinderNode>::iterator& it) {
+sp<IBinder> RpcState::tryEraseNode(std::map<uint64_t, BinderNode>::iterator& it) {
     sp<IBinder> ref;
 
     if (it->second.timesSent == 0) {