From 6e3b01b9c8841f0a27c1d59a2aabad3abf3dde1c Mon Sep 17 00:00:00 2001 From: Amos Jeffries Date: Thu, 17 Jul 2008 05:51:01 -0600 Subject: [PATCH] Author: Henrik Nordstrom userhash and sourcehash peer selection methods These is effectively just copies of carp.cc with changed keying method to key on the authenticated username respectiely client source address. --- src/Makefile.am | 16 +++ src/Makefile.in | 279 +++++++++++++++++++++++------------------ src/cache_cf.cc | 12 ++ src/cf.data.pre | 8 ++ src/enums.h | 2 + src/main.cc | 4 + src/neighbors.cc | 9 ++ src/peer_select.cc | 7 +- src/peer_sourcehash.cc | 228 +++++++++++++++++++++++++++++++++ src/peer_userhash.cc | 233 ++++++++++++++++++++++++++++++++++ src/protos.h | 9 +- src/structs.h | 31 +++-- 12 files changed, 702 insertions(+), 136 deletions(-) create mode 100644 src/peer_sourcehash.cc create mode 100644 src/peer_userhash.cc diff --git a/src/Makefile.am b/src/Makefile.am index 8acdd6ff90..01b2086466 100755 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -543,6 +543,8 @@ squid_SOURCES = \ PeerDigest.h \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ PeerSelectState.h \ PingData.h \ protos.h \ @@ -840,6 +842,8 @@ ufsdump_SOURCES = \ pconn.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ protos.h \ redirect.cc \ referer.cc \ @@ -1361,6 +1365,8 @@ tests_testCacheManager_SOURCES = \ pconn.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ redirect.cc \ referer.cc \ refresh.cc \ @@ -1527,6 +1533,8 @@ tests_testEvent_SOURCES = \ pconn.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ redirect.cc \ referer.cc \ refresh.cc \ @@ -1679,6 +1687,8 @@ tests_testEventLoop_SOURCES = \ pconn.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ redirect.cc \ referer.cc \ refresh.cc \ @@ -1857,6 +1867,8 @@ tests_test_http_range_SOURCES = \ Parsing.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ pconn.cc \ redirect.cc \ referer.cc \ @@ -2014,6 +2026,8 @@ tests_testHttpRequest_SOURCES = \ pconn.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ redirect.cc \ referer.cc \ refresh.cc \ @@ -2353,6 +2367,8 @@ tests_testURL_SOURCES = \ pconn.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ redirect.cc \ referer.cc \ refresh.cc \ diff --git a/src/Makefile.in b/src/Makefile.in index 6fa275bde4..ac4b5dec85 100644 --- a/src/Makefile.in +++ b/src/Makefile.in @@ -247,22 +247,23 @@ am__squid_SOURCES_DIST = access_log.cc AccessLogEntry.h acl.cc \ mem_node.h Mem.h MemBuf.cc MemObject.cc MemObject.h mime.cc \ multicast.cc neighbors.cc net_db.cc Packer.cc Packer.h \ Parsing.cc Parsing.h ProfStats.cc pconn.cc pconn.h \ - PeerDigest.h peer_digest.cc peer_select.cc PeerSelectState.h \ - PingData.h protos.h redirect.cc referer.cc refresh.cc \ - RemovalPolicy.cc RemovalPolicy.h send-announce.cc snmp_core.cc \ - snmp_agent.cc squid.h SquidNew.cc ACLCertificateData.cc \ - ACLCertificateData.h ACLCertificate.cc ACLCertificate.h \ - ssl_support.cc ssl_support.h stat.cc StatHist.cc String.cc \ - stmem.cc stmem.h store.cc Store.h StoreFileSystem.cc \ - StoreFileSystem.h StoreHashIndex.h store_io.cc StoreIOBuffer.h \ - StoreIOState.cc StoreIOState.h store_client.cc StoreClient.h \ - store_digest.cc store_dir.cc store_key_md5.cc store_log.cc \ - store_rebuild.cc store_swapin.cc store_swapmeta.cc \ - store_swapout.cc StoreMeta.cc StoreMeta.h StoreMetaMD5.cc \ - StoreMetaMD5.h StoreMetaSTD.cc StoreMetaSTD.h \ - StoreMetaSTDLFS.cc StoreMetaSTDLFS.h StoreMetaObjSize.h \ - StoreMetaUnpacker.cc StoreMetaUnpacker.h StoreMetaURL.cc \ - StoreMetaURL.h StoreMetaVary.cc StoreMetaVary.h StoreSearch.h \ + PeerDigest.h peer_digest.cc peer_select.cc peer_sourcehash.cc \ + peer_userhash.cc PeerSelectState.h PingData.h protos.h \ + redirect.cc referer.cc refresh.cc RemovalPolicy.cc \ + RemovalPolicy.h send-announce.cc snmp_core.cc snmp_agent.cc \ + squid.h SquidNew.cc ACLCertificateData.cc ACLCertificateData.h \ + ACLCertificate.cc ACLCertificate.h ssl_support.cc \ + ssl_support.h stat.cc StatHist.cc String.cc stmem.cc stmem.h \ + store.cc Store.h StoreFileSystem.cc StoreFileSystem.h \ + StoreHashIndex.h store_io.cc StoreIOBuffer.h StoreIOState.cc \ + StoreIOState.h store_client.cc StoreClient.h store_digest.cc \ + store_dir.cc store_key_md5.cc store_log.cc store_rebuild.cc \ + store_swapin.cc store_swapmeta.cc store_swapout.cc \ + StoreMeta.cc StoreMeta.h StoreMetaMD5.cc StoreMetaMD5.h \ + StoreMetaSTD.cc StoreMetaSTD.h StoreMetaSTDLFS.cc \ + StoreMetaSTDLFS.h StoreMetaObjSize.h StoreMetaUnpacker.cc \ + StoreMetaUnpacker.h StoreMetaURL.cc StoreMetaURL.h \ + StoreMetaVary.cc StoreMetaVary.h StoreSearch.h \ StoreSwapLogData.cc StoreSwapLogData.h Server.cc Server.h \ structs.h SwapDir.cc SwapDir.h time.cc tools.cc tunnel.cc \ typedefs.h unlinkd.cc url.cc URL.h URLScheme.cc URLScheme.h \ @@ -352,7 +353,8 @@ am_squid_OBJECTS = access_log.$(OBJEXT) acl.$(OBJEXT) \ mime.$(OBJEXT) multicast.$(OBJEXT) neighbors.$(OBJEXT) \ net_db.$(OBJEXT) Packer.$(OBJEXT) Parsing.$(OBJEXT) \ $(am__objects_19) pconn.$(OBJEXT) peer_digest.$(OBJEXT) \ - peer_select.$(OBJEXT) redirect.$(OBJEXT) referer.$(OBJEXT) \ + peer_select.$(OBJEXT) peer_sourcehash.$(OBJEXT) \ + peer_userhash.$(OBJEXT) redirect.$(OBJEXT) referer.$(OBJEXT) \ refresh.$(OBJEXT) RemovalPolicy.$(OBJEXT) \ send-announce.$(OBJEXT) $(am__objects_21) SquidNew.$(OBJEXT) \ $(am__objects_23) stat.$(OBJEXT) StatHist.$(OBJEXT) \ @@ -488,15 +490,16 @@ am__tests_testCacheManager_SOURCES_DIST = debug.cc globals.cc \ ipc.cc ipc_win32.cc ipcache.cc int.cc internal.cc list.cc \ logfile.cc multicast.cc mem_node.cc MemBuf.cc MemObject.cc \ mime.cc neighbors.cc net_db.cc Packer.cc Parsing.cc pconn.cc \ - peer_digest.cc peer_select.cc redirect.cc referer.cc \ - refresh.cc RemovalPolicy.cc Server.cc snmp_core.cc \ - snmp_agent.cc ACLCertificateData.cc ACLCertificateData.h \ - ACLCertificate.cc ACLCertificate.h ssl_support.cc \ - ssl_support.h stat.cc StatHist.cc stmem.cc store.cc \ - store_client.cc store_digest.cc store_dir.cc store_io.cc \ - store_key_md5.cc store_log.cc store_rebuild.cc store_swapin.cc \ - store_swapmeta.cc store_swapout.cc StoreFileSystem.cc \ - StoreIOState.cc StoreMeta.cc StoreMetaMD5.cc StoreMetaSTD.cc \ + peer_digest.cc peer_select.cc peer_sourcehash.cc \ + peer_userhash.cc redirect.cc referer.cc refresh.cc \ + RemovalPolicy.cc Server.cc snmp_core.cc snmp_agent.cc \ + ACLCertificateData.cc ACLCertificateData.h ACLCertificate.cc \ + ACLCertificate.h ssl_support.cc ssl_support.h stat.cc \ + StatHist.cc stmem.cc store.cc store_client.cc store_digest.cc \ + store_dir.cc store_io.cc store_key_md5.cc store_log.cc \ + store_rebuild.cc store_swapin.cc store_swapmeta.cc \ + store_swapout.cc StoreFileSystem.cc StoreIOState.cc \ + StoreMeta.cc StoreMetaMD5.cc StoreMetaSTD.cc \ StoreMetaSTDLFS.cc StoreMetaUnpacker.cc StoreMetaURL.cc \ StoreMetaVary.cc StoreSwapLogData.cc tools.cc tunnel.cc \ SwapDir.cc url.cc URLScheme.cc urn.cc useragent.cc wccp2.cc \ @@ -533,7 +536,8 @@ am_tests_testCacheManager_OBJECTS = debug.$(OBJEXT) globals.$(OBJEXT) \ MemBuf.$(OBJEXT) MemObject.$(OBJEXT) mime.$(OBJEXT) \ neighbors.$(OBJEXT) net_db.$(OBJEXT) Packer.$(OBJEXT) \ Parsing.$(OBJEXT) pconn.$(OBJEXT) peer_digest.$(OBJEXT) \ - peer_select.$(OBJEXT) redirect.$(OBJEXT) referer.$(OBJEXT) \ + peer_select.$(OBJEXT) peer_sourcehash.$(OBJEXT) \ + peer_userhash.$(OBJEXT) redirect.$(OBJEXT) referer.$(OBJEXT) \ refresh.$(OBJEXT) RemovalPolicy.$(OBJEXT) Server.$(OBJEXT) \ $(am__objects_21) $(am__objects_23) stat.$(OBJEXT) \ StatHist.$(OBJEXT) stmem.$(OBJEXT) store.$(OBJEXT) \ @@ -710,19 +714,20 @@ am__tests_testEvent_SOURCES_DIST = debug.cc EventLoop.h EventLoop.cc \ ipc.cc ipc_win32.cc ipcache.cc int.cc internal.cc list.cc \ logfile.cc multicast.cc mem_node.cc MemBuf.cc MemObject.cc \ mime.cc neighbors.cc net_db.cc Packer.cc Parsing.cc pconn.cc \ - peer_digest.cc peer_select.cc redirect.cc referer.cc \ - refresh.cc Server.cc snmp_core.cc snmp_agent.cc \ - ACLCertificateData.cc ACLCertificateData.h ACLCertificate.cc \ - ACLCertificate.h ssl_support.cc ssl_support.h stat.cc \ - StatHist.cc stmem.cc store.cc store_client.cc store_digest.cc \ - store_dir.cc store_io.cc store_key_md5.cc store_log.cc \ - store_rebuild.cc store_swapin.cc store_swapmeta.cc \ - store_swapout.cc StoreFileSystem.cc StoreIOState.cc \ - StoreMeta.cc StoreMetaMD5.cc StoreMetaSTD.cc \ - StoreMetaSTDLFS.cc StoreMetaUnpacker.cc StoreMetaURL.cc \ - StoreMetaVary.cc StoreSwapLogData.cc tools.cc tunnel.cc \ - SwapDir.cc url.cc URLScheme.cc urn.cc useragent.cc wccp2.cc \ - whois.cc win32.cc wordlist.cc + peer_digest.cc peer_select.cc peer_sourcehash.cc \ + peer_userhash.cc redirect.cc referer.cc refresh.cc Server.cc \ + snmp_core.cc snmp_agent.cc ACLCertificateData.cc \ + ACLCertificateData.h ACLCertificate.cc ACLCertificate.h \ + ssl_support.cc ssl_support.h stat.cc StatHist.cc stmem.cc \ + store.cc store_client.cc store_digest.cc store_dir.cc \ + store_io.cc store_key_md5.cc store_log.cc store_rebuild.cc \ + store_swapin.cc store_swapmeta.cc store_swapout.cc \ + StoreFileSystem.cc StoreIOState.cc StoreMeta.cc \ + StoreMetaMD5.cc StoreMetaSTD.cc StoreMetaSTDLFS.cc \ + StoreMetaUnpacker.cc StoreMetaURL.cc StoreMetaVary.cc \ + StoreSwapLogData.cc tools.cc tunnel.cc SwapDir.cc url.cc \ + URLScheme.cc urn.cc useragent.cc wccp2.cc whois.cc win32.cc \ + wordlist.cc am_tests_testEvent_OBJECTS = debug.$(OBJEXT) EventLoop.$(OBJEXT) \ globals.$(OBJEXT) HttpRequest.$(OBJEXT) \ HttpRequestMethod.$(OBJEXT) mem.$(OBJEXT) \ @@ -756,7 +761,8 @@ am_tests_testEvent_OBJECTS = debug.$(OBJEXT) EventLoop.$(OBJEXT) \ MemBuf.$(OBJEXT) MemObject.$(OBJEXT) mime.$(OBJEXT) \ neighbors.$(OBJEXT) net_db.$(OBJEXT) Packer.$(OBJEXT) \ Parsing.$(OBJEXT) pconn.$(OBJEXT) peer_digest.$(OBJEXT) \ - peer_select.$(OBJEXT) redirect.$(OBJEXT) referer.$(OBJEXT) \ + peer_select.$(OBJEXT) peer_sourcehash.$(OBJEXT) \ + peer_userhash.$(OBJEXT) redirect.$(OBJEXT) referer.$(OBJEXT) \ refresh.$(OBJEXT) Server.$(OBJEXT) $(am__objects_21) \ $(am__objects_23) stat.$(OBJEXT) StatHist.$(OBJEXT) \ stmem.$(OBJEXT) store.$(OBJEXT) store_client.$(OBJEXT) \ @@ -812,19 +818,20 @@ am__tests_testEventLoop_SOURCES_DIST = debug.cc EventLoop.h \ ipc.cc ipc_win32.cc ipcache.cc int.cc internal.cc list.cc \ logfile.cc multicast.cc mem_node.cc MemBuf.cc MemObject.cc \ mime.cc neighbors.cc net_db.cc Packer.cc Parsing.cc pconn.cc \ - peer_digest.cc peer_select.cc redirect.cc referer.cc \ - refresh.cc Server.cc snmp_core.cc snmp_agent.cc \ - ACLCertificateData.cc ACLCertificateData.h ACLCertificate.cc \ - ACLCertificate.h ssl_support.cc ssl_support.h stat.cc \ - StatHist.cc stmem.cc store.cc store_client.cc store_digest.cc \ - store_dir.cc store_io.cc store_key_md5.cc store_log.cc \ - store_rebuild.cc store_swapin.cc store_swapmeta.cc \ - store_swapout.cc StoreFileSystem.cc StoreIOState.cc \ - StoreMeta.cc StoreMetaMD5.cc StoreMetaSTD.cc \ - StoreMetaSTDLFS.cc StoreMetaUnpacker.cc StoreMetaURL.cc \ - StoreMetaVary.cc StoreSwapLogData.cc tools.cc tunnel.cc \ - SwapDir.cc url.cc URLScheme.cc urn.cc useragent.cc wccp2.cc \ - whois.cc win32.cc wordlist.cc + peer_digest.cc peer_select.cc peer_sourcehash.cc \ + peer_userhash.cc redirect.cc referer.cc refresh.cc Server.cc \ + snmp_core.cc snmp_agent.cc ACLCertificateData.cc \ + ACLCertificateData.h ACLCertificate.cc ACLCertificate.h \ + ssl_support.cc ssl_support.h stat.cc StatHist.cc stmem.cc \ + store.cc store_client.cc store_digest.cc store_dir.cc \ + store_io.cc store_key_md5.cc store_log.cc store_rebuild.cc \ + store_swapin.cc store_swapmeta.cc store_swapout.cc \ + StoreFileSystem.cc StoreIOState.cc StoreMeta.cc \ + StoreMetaMD5.cc StoreMetaSTD.cc StoreMetaSTDLFS.cc \ + StoreMetaUnpacker.cc StoreMetaURL.cc StoreMetaVary.cc \ + StoreSwapLogData.cc tools.cc tunnel.cc SwapDir.cc url.cc \ + URLScheme.cc urn.cc useragent.cc wccp2.cc whois.cc win32.cc \ + wordlist.cc am_tests_testEventLoop_OBJECTS = debug.$(OBJEXT) EventLoop.$(OBJEXT) \ globals.$(OBJEXT) HttpRequest.$(OBJEXT) \ HttpRequestMethod.$(OBJEXT) mem.$(OBJEXT) \ @@ -858,7 +865,8 @@ am_tests_testEventLoop_OBJECTS = debug.$(OBJEXT) EventLoop.$(OBJEXT) \ MemBuf.$(OBJEXT) MemObject.$(OBJEXT) mime.$(OBJEXT) \ neighbors.$(OBJEXT) net_db.$(OBJEXT) Packer.$(OBJEXT) \ Parsing.$(OBJEXT) pconn.$(OBJEXT) peer_digest.$(OBJEXT) \ - peer_select.$(OBJEXT) redirect.$(OBJEXT) referer.$(OBJEXT) \ + peer_select.$(OBJEXT) peer_sourcehash.$(OBJEXT) \ + peer_userhash.$(OBJEXT) redirect.$(OBJEXT) referer.$(OBJEXT) \ refresh.$(OBJEXT) Server.$(OBJEXT) $(am__objects_21) \ $(am__objects_23) stat.$(OBJEXT) StatHist.$(OBJEXT) \ stmem.$(OBJEXT) store.$(OBJEXT) store_client.$(OBJEXT) \ @@ -940,15 +948,16 @@ am__tests_testHttpRequest_SOURCES_DIST = debug.cc globals.cc \ ipc.cc ipc_win32.cc ipcache.cc int.cc internal.cc list.cc \ logfile.cc multicast.cc mem_node.cc MemBuf.cc MemObject.cc \ mime.cc neighbors.cc net_db.cc Packer.cc Parsing.cc pconn.cc \ - peer_digest.cc peer_select.cc redirect.cc referer.cc \ - refresh.cc RemovalPolicy.cc Server.cc snmp_core.cc \ - snmp_agent.cc ACLCertificateData.cc ACLCertificateData.h \ - ACLCertificate.cc ACLCertificate.h ssl_support.cc \ - ssl_support.h stat.cc StatHist.cc stmem.cc store.cc \ - store_client.cc store_digest.cc store_dir.cc store_io.cc \ - store_key_md5.cc store_log.cc store_rebuild.cc store_swapin.cc \ - store_swapmeta.cc store_swapout.cc StoreFileSystem.cc \ - StoreIOState.cc StoreMeta.cc StoreMetaMD5.cc StoreMetaSTD.cc \ + peer_digest.cc peer_select.cc peer_sourcehash.cc \ + peer_userhash.cc redirect.cc referer.cc refresh.cc \ + RemovalPolicy.cc Server.cc snmp_core.cc snmp_agent.cc \ + ACLCertificateData.cc ACLCertificateData.h ACLCertificate.cc \ + ACLCertificate.h ssl_support.cc ssl_support.h stat.cc \ + StatHist.cc stmem.cc store.cc store_client.cc store_digest.cc \ + store_dir.cc store_io.cc store_key_md5.cc store_log.cc \ + store_rebuild.cc store_swapin.cc store_swapmeta.cc \ + store_swapout.cc StoreFileSystem.cc StoreIOState.cc \ + StoreMeta.cc StoreMetaMD5.cc StoreMetaSTD.cc \ StoreMetaSTDLFS.cc StoreMetaUnpacker.cc StoreMetaURL.cc \ StoreMetaVary.cc StoreSwapLogData.cc tools.cc tunnel.cc \ SwapDir.cc url.cc URLScheme.cc urn.cc useragent.cc wccp2.cc \ @@ -985,7 +994,8 @@ am_tests_testHttpRequest_OBJECTS = debug.$(OBJEXT) globals.$(OBJEXT) \ MemBuf.$(OBJEXT) MemObject.$(OBJEXT) mime.$(OBJEXT) \ neighbors.$(OBJEXT) net_db.$(OBJEXT) Packer.$(OBJEXT) \ Parsing.$(OBJEXT) pconn.$(OBJEXT) peer_digest.$(OBJEXT) \ - peer_select.$(OBJEXT) redirect.$(OBJEXT) referer.$(OBJEXT) \ + peer_select.$(OBJEXT) peer_sourcehash.$(OBJEXT) \ + peer_userhash.$(OBJEXT) redirect.$(OBJEXT) referer.$(OBJEXT) \ refresh.$(OBJEXT) RemovalPolicy.$(OBJEXT) Server.$(OBJEXT) \ $(am__objects_21) $(am__objects_23) stat.$(OBJEXT) \ StatHist.$(OBJEXT) stmem.$(OBJEXT) store.$(OBJEXT) \ @@ -1123,19 +1133,19 @@ am__tests_testURL_SOURCES_DIST = debug.cc url.cc URLScheme.cc \ ipc.cc ipc_win32.cc ipcache.cc int.cc internal.cc list.cc \ logfile.cc multicast.cc mem_node.cc MemBuf.cc MemObject.cc \ mime.cc neighbors.cc net_db.cc Packer.cc Parsing.cc pconn.cc \ - peer_digest.cc peer_select.cc redirect.cc referer.cc \ - refresh.cc Server.cc snmp_core.cc snmp_agent.cc \ - ACLCertificateData.cc ACLCertificateData.h ACLCertificate.cc \ - ACLCertificate.h ssl_support.cc ssl_support.h stat.cc \ - StatHist.cc stmem.cc store.cc store_client.cc store_digest.cc \ - store_dir.cc store_io.cc store_key_md5.cc store_log.cc \ - store_rebuild.cc store_swapin.cc store_swapmeta.cc \ - store_swapout.cc StoreFileSystem.cc StoreIOState.cc \ - StoreMeta.cc StoreMetaMD5.cc StoreMetaSTD.cc \ - StoreMetaSTDLFS.cc StoreMetaUnpacker.cc StoreMetaURL.cc \ - StoreMetaVary.cc StoreSwapLogData.cc tools.cc tunnel.cc \ - SwapDir.cc urn.cc useragent.cc wccp2.cc whois.cc win32.cc \ - wordlist.cc + peer_digest.cc peer_select.cc peer_sourcehash.cc \ + peer_userhash.cc redirect.cc referer.cc refresh.cc Server.cc \ + snmp_core.cc snmp_agent.cc ACLCertificateData.cc \ + ACLCertificateData.h ACLCertificate.cc ACLCertificate.h \ + ssl_support.cc ssl_support.h stat.cc StatHist.cc stmem.cc \ + store.cc store_client.cc store_digest.cc store_dir.cc \ + store_io.cc store_key_md5.cc store_log.cc store_rebuild.cc \ + store_swapin.cc store_swapmeta.cc store_swapout.cc \ + StoreFileSystem.cc StoreIOState.cc StoreMeta.cc \ + StoreMetaMD5.cc StoreMetaSTD.cc StoreMetaSTDLFS.cc \ + StoreMetaUnpacker.cc StoreMetaURL.cc StoreMetaVary.cc \ + StoreSwapLogData.cc tools.cc tunnel.cc SwapDir.cc urn.cc \ + useragent.cc wccp2.cc whois.cc win32.cc wordlist.cc am_tests_testURL_OBJECTS = debug.$(OBJEXT) url.$(OBJEXT) \ URLScheme.$(OBJEXT) globals.$(OBJEXT) HttpRequest.$(OBJEXT) \ HttpRequestMethod.$(OBJEXT) mem.$(OBJEXT) \ @@ -1169,7 +1179,8 @@ am_tests_testURL_OBJECTS = debug.$(OBJEXT) url.$(OBJEXT) \ MemBuf.$(OBJEXT) MemObject.$(OBJEXT) mime.$(OBJEXT) \ neighbors.$(OBJEXT) net_db.$(OBJEXT) Packer.$(OBJEXT) \ Parsing.$(OBJEXT) pconn.$(OBJEXT) peer_digest.$(OBJEXT) \ - peer_select.$(OBJEXT) redirect.$(OBJEXT) referer.$(OBJEXT) \ + peer_select.$(OBJEXT) peer_sourcehash.$(OBJEXT) \ + peer_userhash.$(OBJEXT) redirect.$(OBJEXT) referer.$(OBJEXT) \ refresh.$(OBJEXT) Server.$(OBJEXT) $(am__objects_21) \ $(am__objects_23) stat.$(OBJEXT) StatHist.$(OBJEXT) \ stmem.$(OBJEXT) store.$(OBJEXT) store_client.$(OBJEXT) \ @@ -1261,20 +1272,21 @@ am__tests_test_http_range_SOURCES_DIST = tests/test_http_range.cc \ icp_v3.cc ACLIdent.cc ACLIdent.h ident.cc int.cc internal.cc \ ipc.cc ipc_win32.cc ipcache.cc list.cc logfile.cc mem.cc \ mem_node.cc MemObject.cc mime.cc multicast.cc neighbors.cc \ - net_db.cc Parsing.cc peer_digest.cc peer_select.cc pconn.cc \ - redirect.cc referer.cc refresh.cc RemovalPolicy.cc Server.cc \ - snmp_core.cc snmp_agent.cc ACLCertificateData.cc \ - ACLCertificateData.h ACLCertificate.cc ACLCertificate.h \ - ssl_support.cc ssl_support.h stat.cc StatHist.cc stmem.cc \ - store.cc store_client.cc store_digest.cc store_dir.cc \ - store_key_md5.cc store_io.cc store_log.cc store_rebuild.cc \ - store_swapin.cc store_swapmeta.cc store_swapout.cc \ - StoreFileSystem.cc StoreIOState.cc StoreMeta.cc \ - StoreMetaMD5.cc StoreMetaSTD.cc StoreMetaSTDLFS.cc \ - StoreMetaUnpacker.cc StoreMetaURL.cc StoreMetaVary.cc \ - StoreSwapLogData.cc String.cc SwapDir.cc time.cc tools.cc \ - tunnel.cc url.cc URLScheme.cc urn.cc useragent.cc wccp2.cc \ - whois.cc win32.cc wordlist.cc Packer.cc MemBuf.cc + net_db.cc Parsing.cc peer_digest.cc peer_select.cc \ + peer_sourcehash.cc peer_userhash.cc pconn.cc redirect.cc \ + referer.cc refresh.cc RemovalPolicy.cc Server.cc snmp_core.cc \ + snmp_agent.cc ACLCertificateData.cc ACLCertificateData.h \ + ACLCertificate.cc ACLCertificate.h ssl_support.cc \ + ssl_support.h stat.cc StatHist.cc stmem.cc store.cc \ + store_client.cc store_digest.cc store_dir.cc store_key_md5.cc \ + store_io.cc store_log.cc store_rebuild.cc store_swapin.cc \ + store_swapmeta.cc store_swapout.cc StoreFileSystem.cc \ + StoreIOState.cc StoreMeta.cc StoreMetaMD5.cc StoreMetaSTD.cc \ + StoreMetaSTDLFS.cc StoreMetaUnpacker.cc StoreMetaURL.cc \ + StoreMetaVary.cc StoreSwapLogData.cc String.cc SwapDir.cc \ + time.cc tools.cc tunnel.cc url.cc URLScheme.cc urn.cc \ + useragent.cc wccp2.cc whois.cc win32.cc wordlist.cc Packer.cc \ + MemBuf.cc am_tests_test_http_range_OBJECTS = tests/test_http_range.$(OBJEXT) \ access_log.$(OBJEXT) acl.$(OBJEXT) acl_noncore.$(OBJEXT) \ ACLChecklist.$(OBJEXT) ACLProxyAuth.$(OBJEXT) \ @@ -1304,22 +1316,23 @@ am_tests_test_http_range_OBJECTS = tests/test_http_range.$(OBJEXT) \ logfile.$(OBJEXT) mem.$(OBJEXT) mem_node.$(OBJEXT) \ MemObject.$(OBJEXT) mime.$(OBJEXT) multicast.$(OBJEXT) \ neighbors.$(OBJEXT) net_db.$(OBJEXT) Parsing.$(OBJEXT) \ - peer_digest.$(OBJEXT) peer_select.$(OBJEXT) pconn.$(OBJEXT) \ - redirect.$(OBJEXT) referer.$(OBJEXT) refresh.$(OBJEXT) \ - RemovalPolicy.$(OBJEXT) Server.$(OBJEXT) $(am__objects_21) \ - $(am__objects_23) stat.$(OBJEXT) StatHist.$(OBJEXT) \ - stmem.$(OBJEXT) store.$(OBJEXT) store_client.$(OBJEXT) \ - store_digest.$(OBJEXT) store_dir.$(OBJEXT) \ - store_key_md5.$(OBJEXT) store_io.$(OBJEXT) store_log.$(OBJEXT) \ - store_rebuild.$(OBJEXT) store_swapin.$(OBJEXT) \ - store_swapmeta.$(OBJEXT) store_swapout.$(OBJEXT) \ - StoreFileSystem.$(OBJEXT) StoreIOState.$(OBJEXT) \ - StoreMeta.$(OBJEXT) StoreMetaMD5.$(OBJEXT) \ - StoreMetaSTD.$(OBJEXT) StoreMetaSTDLFS.$(OBJEXT) \ - StoreMetaUnpacker.$(OBJEXT) StoreMetaURL.$(OBJEXT) \ - StoreMetaVary.$(OBJEXT) StoreSwapLogData.$(OBJEXT) \ - String.$(OBJEXT) SwapDir.$(OBJEXT) time.$(OBJEXT) \ - tools.$(OBJEXT) tunnel.$(OBJEXT) url.$(OBJEXT) \ + peer_digest.$(OBJEXT) peer_select.$(OBJEXT) \ + peer_sourcehash.$(OBJEXT) peer_userhash.$(OBJEXT) \ + pconn.$(OBJEXT) redirect.$(OBJEXT) referer.$(OBJEXT) \ + refresh.$(OBJEXT) RemovalPolicy.$(OBJEXT) Server.$(OBJEXT) \ + $(am__objects_21) $(am__objects_23) stat.$(OBJEXT) \ + StatHist.$(OBJEXT) stmem.$(OBJEXT) store.$(OBJEXT) \ + store_client.$(OBJEXT) store_digest.$(OBJEXT) \ + store_dir.$(OBJEXT) store_key_md5.$(OBJEXT) store_io.$(OBJEXT) \ + store_log.$(OBJEXT) store_rebuild.$(OBJEXT) \ + store_swapin.$(OBJEXT) store_swapmeta.$(OBJEXT) \ + store_swapout.$(OBJEXT) StoreFileSystem.$(OBJEXT) \ + StoreIOState.$(OBJEXT) StoreMeta.$(OBJEXT) \ + StoreMetaMD5.$(OBJEXT) StoreMetaSTD.$(OBJEXT) \ + StoreMetaSTDLFS.$(OBJEXT) StoreMetaUnpacker.$(OBJEXT) \ + StoreMetaURL.$(OBJEXT) StoreMetaVary.$(OBJEXT) \ + StoreSwapLogData.$(OBJEXT) String.$(OBJEXT) SwapDir.$(OBJEXT) \ + time.$(OBJEXT) tools.$(OBJEXT) tunnel.$(OBJEXT) url.$(OBJEXT) \ URLScheme.$(OBJEXT) urn.$(OBJEXT) useragent.$(OBJEXT) \ wccp2.$(OBJEXT) whois.$(OBJEXT) $(am__objects_25) \ wordlist.$(OBJEXT) Packer.$(OBJEXT) MemBuf.$(OBJEXT) @@ -1368,12 +1381,13 @@ am__ufsdump_SOURCES_DIST = debug.cc int.cc mem.cc store_key_md5.cc \ list.cc logfile.cc mem_node.cc mem_node.h Mem.h MemBuf.cc \ MemObject.cc MemObject.h mime.cc multicast.cc neighbors.cc \ net_db.cc Packer.cc Parsing.cc ProfStats.cc pconn.cc \ - peer_digest.cc peer_select.cc protos.h redirect.cc referer.cc \ - refresh.cc RemovalPolicy.cc send-announce.cc snmp_core.cc \ - snmp_agent.cc squid.h ACLCertificateData.cc \ - ACLCertificateData.h ACLCertificate.cc ACLCertificate.h \ - ssl_support.cc ssl_support.h tunnel.cc Server.cc SquidNew.cc \ - stat.cc StatHist.cc stmem.cc store_io.cc StoreIOBuffer.h \ + peer_digest.cc peer_select.cc peer_sourcehash.cc \ + peer_userhash.cc protos.h redirect.cc referer.cc refresh.cc \ + RemovalPolicy.cc send-announce.cc snmp_core.cc snmp_agent.cc \ + squid.h ACLCertificateData.cc ACLCertificateData.h \ + ACLCertificate.cc ACLCertificate.h ssl_support.cc \ + ssl_support.h tunnel.cc Server.cc SquidNew.cc stat.cc \ + StatHist.cc stmem.cc store_io.cc StoreIOBuffer.h \ StoreIOState.cc store_client.cc StoreClient.h store_digest.cc \ store_dir.cc store_log.cc store_rebuild.cc store_swapin.cc \ store_swapmeta.cc store_swapout.cc structs.h SwapDir.cc \ @@ -1416,14 +1430,15 @@ am_ufsdump_OBJECTS = debug.$(OBJEXT) int.$(OBJEXT) mem.$(OBJEXT) \ MemObject.$(OBJEXT) mime.$(OBJEXT) multicast.$(OBJEXT) \ neighbors.$(OBJEXT) net_db.$(OBJEXT) Packer.$(OBJEXT) \ Parsing.$(OBJEXT) $(am__objects_19) pconn.$(OBJEXT) \ - peer_digest.$(OBJEXT) peer_select.$(OBJEXT) redirect.$(OBJEXT) \ - referer.$(OBJEXT) refresh.$(OBJEXT) RemovalPolicy.$(OBJEXT) \ - send-announce.$(OBJEXT) $(am__objects_21) $(am__objects_23) \ - tunnel.$(OBJEXT) Server.$(OBJEXT) SquidNew.$(OBJEXT) \ - stat.$(OBJEXT) StatHist.$(OBJEXT) stmem.$(OBJEXT) \ - store_io.$(OBJEXT) StoreIOState.$(OBJEXT) \ - store_client.$(OBJEXT) store_digest.$(OBJEXT) \ - store_dir.$(OBJEXT) store_log.$(OBJEXT) \ + peer_digest.$(OBJEXT) peer_select.$(OBJEXT) \ + peer_sourcehash.$(OBJEXT) peer_userhash.$(OBJEXT) \ + redirect.$(OBJEXT) referer.$(OBJEXT) refresh.$(OBJEXT) \ + RemovalPolicy.$(OBJEXT) send-announce.$(OBJEXT) \ + $(am__objects_21) $(am__objects_23) tunnel.$(OBJEXT) \ + Server.$(OBJEXT) SquidNew.$(OBJEXT) stat.$(OBJEXT) \ + StatHist.$(OBJEXT) stmem.$(OBJEXT) store_io.$(OBJEXT) \ + StoreIOState.$(OBJEXT) store_client.$(OBJEXT) \ + store_digest.$(OBJEXT) store_dir.$(OBJEXT) store_log.$(OBJEXT) \ store_rebuild.$(OBJEXT) store_swapin.$(OBJEXT) \ store_swapmeta.$(OBJEXT) store_swapout.$(OBJEXT) \ SwapDir.$(OBJEXT) tools.$(OBJEXT) $(am__objects_24) \ @@ -2183,6 +2198,8 @@ squid_SOURCES = \ PeerDigest.h \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ PeerSelectState.h \ PingData.h \ protos.h \ @@ -2465,6 +2482,8 @@ ufsdump_SOURCES = \ pconn.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ protos.h \ redirect.cc \ referer.cc \ @@ -2848,6 +2867,8 @@ tests_testCacheManager_SOURCES = \ pconn.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ redirect.cc \ referer.cc \ refresh.cc \ @@ -3018,6 +3039,8 @@ tests_testEvent_SOURCES = \ pconn.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ redirect.cc \ referer.cc \ refresh.cc \ @@ -3172,6 +3195,8 @@ tests_testEventLoop_SOURCES = \ pconn.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ redirect.cc \ referer.cc \ refresh.cc \ @@ -3349,6 +3374,8 @@ tests_test_http_range_SOURCES = \ Parsing.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ pconn.cc \ redirect.cc \ referer.cc \ @@ -3507,6 +3534,8 @@ tests_testHttpRequest_SOURCES = \ pconn.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ redirect.cc \ referer.cc \ refresh.cc \ @@ -3855,6 +3884,8 @@ tests_testURL_SOURCES = \ pconn.cc \ peer_digest.cc \ peer_select.cc \ + peer_sourcehash.cc \ + peer_userhash.cc \ redirect.cc \ referer.cc \ refresh.cc \ @@ -4784,6 +4815,8 @@ distclean-compile: @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/pconn.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/peer_digest.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/peer_select.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/peer_sourcehash.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/peer_userhash.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/pinger.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/recv-announce.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@./$(DEPDIR)/redirect.Po@am__quote@ diff --git a/src/cache_cf.cc b/src/cache_cf.cc index 8756b4a9bc..6b3e6b33dd 100644 --- a/src/cache_cf.cc +++ b/src/cache_cf.cc @@ -1723,6 +1723,18 @@ parse_peer(peer ** head) p->options.carp = 1; #endif + } else if (!strcasecmp(token, "userhash")) { + if (p->type != PEER_PARENT) + fatalf("parse_peer: non-parent userhash peer %s/%d\n", p->host, p->http_port); + + p->options.userhash = 1; + + } else if (!strcasecmp(token, "sourcehash")) { + if (p->type != PEER_PARENT) + fatalf("parse_peer: non-parent sourcehash peer %s/%d\n", p->host, p->http_port); + + p->options.sourcehash = 1; + #if DELAY_POOLS } else if (!strcasecmp(token, "no-delay")) { diff --git a/src/cf.data.pre b/src/cf.data.pre index 5aec56248e..e5ef4c3982 100644 --- a/src/cf.data.pre +++ b/src/cf.data.pre @@ -1311,6 +1311,8 @@ DOC_START round-robin weighted-round-robin carp + userhash + sourcehash multicast-responder closest-only no-digest @@ -1385,6 +1387,12 @@ DOC_START distributed among the parents based on the CARP load balancing hash function based on their weight. + use 'userhash' to load-balance amongst a set of parents + based on the client proxy_auth or ident username. + + use 'sourcehash' to load-balance amongst a set of parents + based on the client source ip. + 'multicast-responder' indicates the named peer is a member of a multicast group. ICP queries will not be sent directly to the peer, but ICP replies diff --git a/src/enums.h b/src/enums.h index b630635f18..2b68f67b53 100644 --- a/src/enums.h +++ b/src/enums.h @@ -176,6 +176,8 @@ typedef enum { CARP, #endif ANY_OLD_PARENT, + USERHASH_PARENT, + SOURCEHASH_PARENT, HIER_MAX } hier_code; diff --git a/src/main.cc b/src/main.cc index 7dce882a98..1f7a52f7c9 100644 --- a/src/main.cc +++ b/src/main.cc @@ -567,6 +567,8 @@ serverConnectionsOpen(void) carpInit(); #endif + peerUserHashInit(); + peerSourceHashInit(); } void @@ -912,6 +914,8 @@ mainInitialize(void) carpRegisterWithCacheManager(manager); #endif + peerUserHashRegisterWithCacheManager(manager); + peerSourceHashRegisterWithCacheManager(manager); cbdataRegisterWithCacheManager(manager); /* These use separate calls so that the comm loops can eventually * coexist. diff --git a/src/neighbors.cc b/src/neighbors.cc index a0ade0e384..b14ba8c065 100644 --- a/src/neighbors.cc +++ b/src/neighbors.cc @@ -1574,6 +1574,15 @@ dump_peer_options(StoreEntry * sentry, peer * p) if (p->options.roundrobin) storeAppendPrintf(sentry, " round-robin"); + if (p->options.carp) + storeAppendPrintf(sentry, " carp"); + + if (p->options.userhash) + storeAppendPrintf(sentry, " userhash"); + + if (p->options.userhash) + storeAppendPrintf(sentry, " sourcehash"); + if (p->options.weighted_roundrobin) storeAppendPrintf(sentry, " weighted-round-robin"); diff --git a/src/peer_select.cc b/src/peer_select.cc index 6ffd0e2173..56c7e78052 100644 --- a/src/peer_select.cc +++ b/src/peer_select.cc @@ -67,6 +67,8 @@ const char *hier_strings[] = "CARP", #endif "ANY_PARENT", + "USERHASH", + "SOURCEHASH", "INVALID CODE" }; @@ -513,8 +515,11 @@ peerGetSomeParent(ps_state * ps) if ((p = getDefaultParent(request))) { code = DEFAULT_PARENT; + } else if ((p = peerUserHashSelectParent(request))) { + code = USERHASH_PARENT; + } else if ((p = peerSourceHashSelectParent(request))) { + code = SOURCEHASH_PARENT; #if USE_CARP - } else if ((p = carpSelectParent(request))) { code = CARP; #endif diff --git a/src/peer_sourcehash.cc b/src/peer_sourcehash.cc new file mode 100644 index 0000000000..a52f920ac4 --- /dev/null +++ b/src/peer_sourcehash.cc @@ -0,0 +1,228 @@ + +/* + * $Id: carp.cc,v 1.27 2008/01/14 12:13:49 hno Exp $ + * + * DEBUG: section 39 Peer source hash based selection + * AUTHOR: Henrik Nordstrom + * BASED ON: carp.cc + * + * SQUID Web Proxy Cache http://www.squid-cache.org/ + * ---------------------------------------------------------- + * + * Squid is the result of efforts by numerous individuals from + * the Internet community; see the CONTRIBUTORS file for full + * details. Many organizations have provided support for Squid's + * development; see the SPONSORS file for full details. Squid is + * Copyrighted (C) 2001 by the Regents of the University of + * California; see the COPYRIGHT file for full details. Squid + * incorporates software developed and/or copyrighted by other + * sources; see the CREDITS file for full details. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. + * + */ + +#include "squid.h" +#include "CacheManager.h" +#include "Store.h" +#include "HttpRequest.h" + +#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) + +static int n_sourcehash_peers = 0; +static peer **sourcehash_peers = NULL; +static OBJH peerSourceHashCachemgr; + +static int +peerSortWeight(const void *a, const void *b) +{ + const peer *const *p1 = (const peer *const *)a; + const peer *const *p2 = (const peer *const *)b; + return (*p1)->weight - (*p2)->weight; +} + +void +peerSourceHashInit(void) +{ + int W = 0; + int K; + int k; + double P_last, X_last, Xn; + peer *p; + peer **P; + char *t; + /* Clean up */ + + for (k = 0; k < n_sourcehash_peers; k++) { + cbdataReferenceDone(sourcehash_peers[k]); + } + + safe_free(sourcehash_peers); + n_sourcehash_peers = 0; + /* find out which peers we have */ + + for (p = Config.peers; p; p = p->next) { + if (!p->options.sourcehash) + continue; + + assert(p->type == PEER_PARENT); + + if (p->weight == 0) + continue; + + n_sourcehash_peers++; + + W += p->weight; + } + + if (n_sourcehash_peers == 0) + return; + + sourcehash_peers = (peer **)xcalloc(n_sourcehash_peers, sizeof(*sourcehash_peers)); + + /* Build a list of the found peers and calculate hashes and load factors */ + for (P = sourcehash_peers, p = Config.peers; p; p = p->next) { + if (!p->options.sourcehash) + continue; + + if (p->weight == 0) + continue; + + /* calculate this peers hash */ + p->sourcehash.hash = 0; + + for (t = p->name; *t != 0; t++) + p->sourcehash.hash += ROTATE_LEFT(p->sourcehash.hash, 19) + (unsigned int) *t; + + p->sourcehash.hash += p->sourcehash.hash * 0x62531965; + + p->sourcehash.hash = ROTATE_LEFT(p->sourcehash.hash, 21); + + /* and load factor */ + p->sourcehash.load_factor = ((double) p->weight) / (double) W; + + if (floor(p->sourcehash.load_factor * 1000.0) == 0.0) + p->sourcehash.load_factor = 0.0; + + /* add it to our list of peers */ + *P++ = cbdataReference(p); + } + + /* Sort our list on weight */ + qsort(sourcehash_peers, n_sourcehash_peers, sizeof(*sourcehash_peers), peerSortWeight); + + /* Calculate the load factor multipliers X_k + * + * X_1 = pow ((K*p_1), (1/K)) + * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1}) + * X_k += pow ((X_{k-1}, {K-k+1}) + * X_k = pow (X_k, {1/(K-k+1)}) + * simplified to have X_1 part of the loop + */ + K = n_sourcehash_peers; + + P_last = 0.0; /* Empty P_0 */ + + Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */ + + X_last = 0.0; /* Empty X_0, nullifies the first pow statement */ + + for (k = 1; k <= K; k++) { + double Kk1 = (double) (K - k + 1); + p = sourcehash_peers[k - 1]; + p->sourcehash.load_multiplier = (Kk1 * (p->sourcehash.load_factor - P_last)) / Xn; + p->sourcehash.load_multiplier += pow(X_last, Kk1); + p->sourcehash.load_multiplier = pow(p->sourcehash.load_multiplier, 1.0 / Kk1); + Xn *= p->sourcehash.load_multiplier; + X_last = p->sourcehash.load_multiplier; + P_last = p->sourcehash.load_factor; + } +} + +void +peerSourceHashRegisterWithCacheManager(CacheManager & manager) +{ + manager.registerAction("sourcehash", "peer sourcehash information", peerSourceHashCachemgr, 0, 1); +} + +peer * +peerSourceHashSelectParent(HttpRequest * request) +{ + int k; + const char *c; + peer *p = NULL; + peer *tp; + unsigned int user_hash = 0; + unsigned int combined_hash; + double score; + double high_score = 0; + const char *key = NULL; + + if (n_sourcehash_peers == 0) + return NULL; + + key = inet_ntoa(request->client_addr); + + /* calculate hash key */ + debugs(39, 2, "peerSourceHashSelectParent: Calculating hash for " << key); + + for (c = key; *c != 0; c++) + user_hash += ROTATE_LEFT(user_hash, 19) + *c; + + /* select peer */ + for (k = 0; k < n_sourcehash_peers; k++) { + tp = sourcehash_peers[k]; + combined_hash = (user_hash ^ tp->sourcehash.hash); + combined_hash += combined_hash * 0x62531965; + combined_hash = ROTATE_LEFT(combined_hash, 21); + score = combined_hash * tp->sourcehash.load_multiplier; + debugs(39, 3, "peerSourceHashSelectParent: " << tp->name << " combined_hash " << combined_hash << + " score " << std::setprecision(0) << score); + + if ((score > high_score) && peerHTTPOkay(tp, request)) { + p = tp; + high_score = score; + } + } + + if (p) + debugs(39, 2, "peerSourceHashSelectParent: selected " << p->name); + + return p; +} + +static void +peerSourceHashCachemgr(StoreEntry * sentry) +{ + peer *p; + int sumfetches = 0; + storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n", + "Hostname", + "Hash", + "Multiplier", + "Factor", + "Actual"); + + for (p = Config.peers; p; p = p->next) + sumfetches += p->stats.fetches; + + for (p = Config.peers; p; p = p->next) { + storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n", + p->name, p->sourcehash.hash, + p->sourcehash.load_multiplier, + p->sourcehash.load_factor, + sumfetches ? (double) p->stats.fetches / sumfetches : -1.0); + } +} diff --git a/src/peer_userhash.cc b/src/peer_userhash.cc new file mode 100644 index 0000000000..d484ade69b --- /dev/null +++ b/src/peer_userhash.cc @@ -0,0 +1,233 @@ + +/* + * $Id: carp.cc,v 1.27 2008/01/14 12:13:49 hno Exp $ + * + * DEBUG: section 39 Peer user hash based selection + * AUTHOR: Henrik Nordstrom + * BASED ON: carp.cc + * + * SQUID Web Proxy Cache http://www.squid-cache.org/ + * ---------------------------------------------------------- + * + * Squid is the result of efforts by numerous individuals from + * the Internet community; see the CONTRIBUTORS file for full + * details. Many organizations have provided support for Squid's + * development; see the SPONSORS file for full details. Squid is + * Copyrighted (C) 2001 by the Regents of the University of + * California; see the COPYRIGHT file for full details. Squid + * incorporates software developed and/or copyrighted by other + * sources; see the CREDITS file for full details. + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 2 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software + * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111, USA. + * + */ + +#include "squid.h" +#include "CacheManager.h" +#include "Store.h" +#include "HttpRequest.h" +#include "AuthUserRequest.h" + +#define ROTATE_LEFT(x, n) (((x) << (n)) | ((x) >> (32-(n)))) + +static int n_userhash_peers = 0; +static peer **userhash_peers = NULL; +static OBJH peerUserHashCachemgr; + +static int +peerSortWeight(const void *a, const void *b) +{ + const peer *const *p1 = (const peer *const *)a; + const peer *const *p2 = (const peer *const *)b; + return (*p1)->weight - (*p2)->weight; +} + +void +peerUserHashInit(void) +{ + int W = 0; + int K; + int k; + double P_last, X_last, Xn; + peer *p; + peer **P; + char *t; + /* Clean up */ + + for (k = 0; k < n_userhash_peers; k++) { + cbdataReferenceDone(userhash_peers[k]); + } + + safe_free(userhash_peers); + n_userhash_peers = 0; + /* find out which peers we have */ + + for (p = Config.peers; p; p = p->next) { + if (!p->options.userhash) + continue; + + assert(p->type == PEER_PARENT); + + if (p->weight == 0) + continue; + + n_userhash_peers++; + + W += p->weight; + } + + if (n_userhash_peers == 0) + return; + + userhash_peers = (peer **)xcalloc(n_userhash_peers, sizeof(*userhash_peers)); + + /* Build a list of the found peers and calculate hashes and load factors */ + for (P = userhash_peers, p = Config.peers; p; p = p->next) { + if (!p->options.userhash) + continue; + + if (p->weight == 0) + continue; + + /* calculate this peers hash */ + p->userhash.hash = 0; + + for (t = p->name; *t != 0; t++) + p->userhash.hash += ROTATE_LEFT(p->userhash.hash, 19) + (unsigned int) *t; + + p->userhash.hash += p->userhash.hash * 0x62531965; + + p->userhash.hash = ROTATE_LEFT(p->userhash.hash, 21); + + /* and load factor */ + p->userhash.load_factor = ((double) p->weight) / (double) W; + + if (floor(p->userhash.load_factor * 1000.0) == 0.0) + p->userhash.load_factor = 0.0; + + /* add it to our list of peers */ + *P++ = cbdataReference(p); + } + + /* Sort our list on weight */ + qsort(userhash_peers, n_userhash_peers, sizeof(*userhash_peers), peerSortWeight); + + /* Calculate the load factor multipliers X_k + * + * X_1 = pow ((K*p_1), (1/K)) + * X_k = ([K-k+1] * [P_k - P_{k-1}])/(X_1 * X_2 * ... * X_{k-1}) + * X_k += pow ((X_{k-1}, {K-k+1}) + * X_k = pow (X_k, {1/(K-k+1)}) + * simplified to have X_1 part of the loop + */ + K = n_userhash_peers; + + P_last = 0.0; /* Empty P_0 */ + + Xn = 1.0; /* Empty starting point of X_1 * X_2 * ... * X_{x-1} */ + + X_last = 0.0; /* Empty X_0, nullifies the first pow statement */ + + for (k = 1; k <= K; k++) { + double Kk1 = (double) (K - k + 1); + p = userhash_peers[k - 1]; + p->userhash.load_multiplier = (Kk1 * (p->userhash.load_factor - P_last)) / Xn; + p->userhash.load_multiplier += pow(X_last, Kk1); + p->userhash.load_multiplier = pow(p->userhash.load_multiplier, 1.0 / Kk1); + Xn *= p->userhash.load_multiplier; + X_last = p->userhash.load_multiplier; + P_last = p->userhash.load_factor; + } +} + +void +peerUserHashRegisterWithCacheManager(CacheManager & manager) +{ + manager.registerAction("userhash", "peer userhash information", peerUserHashCachemgr, 0, 1); +} + +peer * +peerUserHashSelectParent(HttpRequest * request) +{ + int k; + const char *c; + peer *p = NULL; + peer *tp; + unsigned int user_hash = 0; + unsigned int combined_hash; + double score; + double high_score = 0; + const char *key = NULL; + + if (n_userhash_peers == 0) + return NULL; + + if (request->auth_user_request) + key = request->auth_user_request->username(); + + if (!key) + return NULL; + + /* calculate hash key */ + debugs(39, 2, "peerUserHashSelectParent: Calculating hash for " << key); + + for (c = key; *c != 0; c++) + user_hash += ROTATE_LEFT(user_hash, 19) + *c; + + /* select peer */ + for (k = 0; k < n_userhash_peers; k++) { + tp = userhash_peers[k]; + combined_hash = (user_hash ^ tp->userhash.hash); + combined_hash += combined_hash * 0x62531965; + combined_hash = ROTATE_LEFT(combined_hash, 21); + score = combined_hash * tp->userhash.load_multiplier; + debugs(39, 3, "peerUserHashSelectParent: " << tp->name << " combined_hash " << combined_hash << + " score " << std::setprecision(0) << score); + + if ((score > high_score) && peerHTTPOkay(tp, request)) { + p = tp; + high_score = score; + } + } + + if (p) + debugs(39, 2, "peerUserHashSelectParent: selected " << p->name); + + return p; +} + +static void +peerUserHashCachemgr(StoreEntry * sentry) +{ + peer *p; + int sumfetches = 0; + storeAppendPrintf(sentry, "%24s %10s %10s %10s %10s\n", + "Hostname", + "Hash", + "Multiplier", + "Factor", + "Actual"); + + for (p = Config.peers; p; p = p->next) + sumfetches += p->stats.fetches; + + for (p = Config.peers; p; p = p->next) { + storeAppendPrintf(sentry, "%24s %10x %10f %10f %10f\n", + p->name, p->userhash.hash, + p->userhash.load_multiplier, + p->userhash.load_factor, + sumfetches ? (double) p->stats.fetches / sumfetches : -1.0); + } +} diff --git a/src/protos.h b/src/protos.h index a47aeb98cd..8d438ff466 100644 --- a/src/protos.h +++ b/src/protos.h @@ -706,10 +706,17 @@ SQUIDCEXTERN int internalHostnameIs(const char *); #if USE_CARP SQUIDCEXTERN void carpInit(void); -extern void carpRegisterWithCacheManager(CacheManager & manager); +SQUIDCEXTERN void carpRegisterWithCacheManager(CacheManager & manager); SQUIDCEXTERN peer *carpSelectParent(HttpRequest *); #endif +SQUIDCEXTERN void peerUserHashInit(void); +SQUIDCEXTERN void peerUserHashRegisterWithCacheManager(CacheManager & manager); +SQUIDCEXTERN peer * peerUserHashSelectParent(HttpRequest * request); + +SQUIDCEXTERN void peerSourceHashInit(void); +SQUIDCEXTERN void peerSourceHashRegisterWithCacheManager(CacheManager & manager); +SQUIDCEXTERN peer * peerSourceHashSelectParent(HttpRequest * request); #if USE_LEAKFINDER SQUIDCEXTERN void leakInit(void); diff --git a/src/structs.h b/src/structs.h index f7901a85b6..c767db43c8 100755 --- a/src/structs.h +++ b/src/structs.h @@ -1064,20 +1064,15 @@ unsigned int no_netdb_exchange: unsigned int no_delay: 1; #endif - -unsigned int allow_miss: - 1; + unsigned int allow_miss:1; #if USE_CARP - -unsigned int carp: - 1; + unsigned int carp:1; #endif + unsigned int userhash:1; + unsigned int sourcehash:1; + unsigned int originserver:1; + } options; -unsigned int originserver: - 1; - } - - options; int weight; int basetime; @@ -1129,6 +1124,20 @@ unsigned int counting: carp; #endif + struct + { + unsigned int hash; + double load_multiplier; + double load_factor; /* normalized weight value */ + } userhash; + + struct + { + unsigned int hash; + double load_multiplier; + double load_factor; /* normalized weight value */ + } sourcehash; + char *login; /* Proxy authorization */ time_t connect_timeout; int max_conn; -- 2.47.2